Sharpay and Ryan are aspiring Broadway actors. Both will do anything it takes to climb the ladder of success.

For example, consider this ladder right here—well, actually, it's more like a staircase. The "ladder" consists of n steps arranged in a row, whose heights are h1, h2, h3, ..., hn from left to right. To them, a ladder is fabulosa if the height of each non-boundary step is the average of the heights of the steps to its left and right. Formally, hi = (hi-1 + hi+1) / 2 should hold for every i such that 1 < i < n.

In order to make their ladder fabulosa, they have two kinds of operations:

• Jump and Hop: Choose two consecutive steps and make each of them +1 unit higher.
• Bop Bop Bop: Choose three consecutive steps and make each of them +1 unit higher.

Is it possible to make their ladder fabulosa using only these two operations?

Note that the minimum-height step doesn't have to be the leftmost one.

Input Format

The first line of input contains an integer t, the number of test cases. The descriptions of t test cases follow.

Each test case consists of two lines. The first line contains the integer n. The second line contains n integers h1, h2, ..., hn.

Output Format

For each test case, output a single line containing either YES or NO depending on whether the task is possible or not.

Note: The strings in the output are case-sensitive.

Constraints

• 1 ≤ t ≤ 25000
• 2 ≤ n ≤ 105
• The sum of the ns in a single test file is ≤ 105
• 1 ≤ hi ≤ 105

Sample

Input

5
3
6 6 6
3
6 9 12
3
12 9 6
6
2 3 5 7 11 13
8
2 3 5 7 11 13 17 19

Output

YES
YES
YES
YES
YES

Explanation

The ladders in the first three test cases are already fabulosa, so they can be made fabulosa with zero moves.

For the fourth test case, the heights of the n = 6 steps are: [2, 3, 5, 7, 11, 13]. It can be made fabulosa as follows:

• Bop Bop Bop from steps 1 thru 3. The heights become [3, 4, 6, 7, 11, 13].
• Jump and Hop from steps 1 and 2. The heights become [4, 5, 6, 7, 11, 13].
• Jump and Hop from steps 3 and 4. The heights become [4, 5, 7, 8, 11, 13].
• Jump and Hop from steps 3 and 4. The heights become [4, 5, 8, 9, 11, 13].
• Jump and Hop from steps 3 and 4. The heights become [4, 5, 9, 10, 11, 13].
• Jump and Hop from steps 5 and 6. The heights become [4, 5, 9, 10, 12, 14].
• Jump and Hop from steps 1 and 2. The heights become [5, 6, 9, 10, 12, 14].
• Bop Bop Bop from steps 4 thru 6. The heights become [5, 6, 9, 11, 13, 15].
• Jump and Hop from steps 5 and 6. The heights become [5, 6, 9, 11, 14, 16].
• Jump and Hop from steps 1 and 2. The heights become [6, 7, 9, 11, 14, 16].
• Bop Bop Bop from steps 2 thru 4. The heights become [6, 8, 10, 12, 14, 16].

Note that the ladder is now fabulosa.