During cleaning the coast, Alice found n piles of stones. The i-th pile has a_i stones.

Piles i and i + 1 are neighbouring for all 1 ≤ i ≤ n - 1. If pile i becomes empty, piles i - 1 and i + 1 doesn't become neighbouring.

Alice is too lazy to remove these stones, so she asked you to take this duty. She allowed you to do only the following operation: 

  * Select two neighboring piles and, if both of them are not empty, remove one stone from each of them. 



Alice understands that sometimes it's impossible to remove all stones with the given operation, so she allowed you to use the following superability: 

  * Before the start of cleaning, you can select two neighboring piles and swap them. 



Determine, if it is possible to remove all stones using the superability not more than once.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The first line of each test case contains the single integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of piles.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the number of stones in each pile.

It is guaranteed that the total sum of n over all test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print YES or NO — is it possible to remove all stones using the superability not more than once or not.

Example

Input


5
3
1 2 1
3
1 1 2
5
2 2 2 1 3
5
2100 1900 1600 3000 1600
2
2443 2445


Output


YES
YES
YES
YES
NO

Note

In the first test case, you can remove all stones without using a superability: [1, 2, 1] → [1, 1, 0] → [0, 0, 0].

In the second test case, you can apply superability to the second and the third piles and then act like in the first testcase.

In the third test case, you can apply superability to the fourth and the fifth piles, thus getting a = [2, 2, 2, 3, 1].

In the fourth test case, you can apply superability to the first and the second piles, thus getting a = [1900, 2100, 1600, 3000, 1600].
#!/usr/bin/env python3
import sys, getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline  # to read input quickly

# available on Google, AtCoder Python3, not available on Codeforces
# import numpy as np
# import scipy

M9 = 10**9 + 7  # 998244353
# d4 = [(1,0),(0,1),(-1,0),(0,-1)]
# d8 = [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]
# d6 = [(2,0),(1,1),(-1,1),(-2,0),(-1,-1),(1,-1)]  # hexagonal layout
MAXINT = sys.maxsize

# if testing locally, print to terminal with a different color
OFFLINE_TEST = getpass.getuser() == "hkmac"
# OFFLINE_TEST = False  # codechef does not allow getpass
def log(*args):
    if OFFLINE_TEST:
        print('\033[36m', *args, '\033[0m', file=sys.stderr)

def solve(*args):
    # screen input
    if OFFLINE_TEST:
        log("----- solving ------")
        log(*args)
        log("----- ------- ------")
    return solve_(*args)

def read_matrix(rows):
    return [list(map(int,input().split())) for _ in range(rows)]

def read_strings(rows):
    return [input().strip() for _ in range(rows)]

# ---------------------------- template ends here ----------------------------

def check(lst):
    remainder = lst[0]
    for x in lst[1:]:
        remainder = x - remainder
        if remainder < 0:
            return False
    else:  # ok without swap
        if remainder == 0:
            return True
    return False

def remainder_arr(lst):
    remainder = lst[0]
    remainders = [0,lst[0]]
    faulty = False
    for x in lst[1:]:
        remainder = x - remainder
        if faulty:
            remainder = -1
        remainders.append(remainder)
        if remainder < 0:
            faulty = True
            
    return remainders

def solve_(arr, reverse=False):
    # sweep, if cannot, replace

    if check(arr):
        log("no swap")
        return "YES"

    remainder = arr[0]
    for i,x in enumerate(arr[1:], start=1):
        remainder = x - remainder
        if remainder < 0:
            # swap with either before or after
            arr[i], arr[i-1] = arr[i-1], arr[i]
            if check(arr):
                log("left swap")
                return "YES"
            arr[i], arr[i-1] = arr[i-1], arr[i]
            break

    arr[-2], arr[-1] = arr[-1], arr[-2]
    if check(arr):
        log("end swap")
        return "YES"
    arr[-2], arr[-1] = arr[-1], arr[-2]

    xrr = remainder_arr(arr)
    yrr = remainder_arr(arr[::-1])[::-1]
    log(xrr)
    log(yrr)

    remainder = 0
    # if I swap, what is the remainder
    for i,(x,y) in enumerate(zip(arr, arr[1:])):
        if x-remainder > y:  # must swap, would have swapped
            break
        new_remainder = x-(y-remainder)
        log(x,y,new_remainder,yrr[i+2])
        if new_remainder >= 0 and yrr[i+2] == new_remainder:
            arr[i], arr[i+1] = arr[i+1], arr[i]
            if check(arr):
                log("advanced swap")
                return "YES"
            arr[i], arr[i+1] = arr[i+1], arr[i]
        remainder = x-remainder
        # log(remainder, "r")

    if not reverse:
        log("reversing")
        return solve_(arr[::-1], reverse=True)


    return "NO"


# for case_num in [0]:  # no loop over test case
# for case_num in range(100):  # if the number of test cases is specified
for case_num in range(int(input())):

    # read line as an integer
    k = int(input())

    # read line as a string
    # srr = input().strip()

    # read one line and parse each word as a string
    # lst = input().split()
    
    # read one line and parse each word as an integer
    # a,b,c = list(map(int,input().split()))
    lst = list(map(int,input().split()))

    # read multiple rows
    # mrr = read_matrix(k)  # and return as a list of list of int
    # arr = read_strings(k)  # and return as a list of str

    res = solve(lst)  # include input here
    
    # print result
    # Google and Facebook - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Other platforms - no case number required
    print(res)
    # print(len(res))
    # print(*res)  # print a list with elements
    # for r in res:  # print each list in a different line
        # print(res)
        # print(*res)