In Bajtosia's kindergarten, there are many toys, and it is sometimes difficult for the girl to decide which one she will play with on a given day. To make her choice easier, Bajtosia decided to use counting-out rhymes.

If she wants to choose one of $n$ toys on a given day, she arranges them all in a row and numbers them from 1 to $n$. She starts by pointing at one of the toys, then recites the rhyme, and with each syllable, she moves to the previous or next toy in the row (in the case of toy 1 and $n$, she has no choice and must move to 2 and $n-1$, respectively). She plays with the last toy pointed at for the rest of the day.

During the counting-out rhyme, Bajtosia tracks how many times she points at each toy: after finishing the rhyme, the $i$-th toy has been pointed at $a_i$ times. Check if Bajtosia made a mistake, i.e., for a given sequence $a_1, a_2, \dots, a_n$ remembered by Bajtosia, determine if there exists a counting-out rhyme that matches it.

This situation repeated for $t$ days with different subsets of toys and different counting-out rhymes.

Input

The first line contains an integer $t$ ($1 \le t \le 100\,000$), representing the number of days Bajtosia used counting-out rhymes to choose a toy. Then, $t$ descriptions of individual days follow, one after another.

The first line of each day's description contains a single integer $n$ ($1 \le n \le 1\,000\,000$), representing the number of toys participating in the counting-out rhyme that day. The second line contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), representing how many times the consecutive toys were pointed at during the rhyme according to Bajtosia.

You may assume that at least one of the numbers $a_i$ is non-zero.

The sum of all values of $n$ over all $t$ days does not exceed $1\,000\,000$.

Output

Output $t$ lines, each containing one of the words TAK or NIE. The word TAK means that there exists a counting-out rhyme matching the sequence remembered by Bajtosia, and the word NIE means that no such rhyme exists.

Examples

Input 1

7
3
1 3 1
2
5 7
3
0 1 0
1
2
6
3 3 2 1 0 0
5
1 3 2 2 3
3
1 0 1

Output 1

TAK
NIE
TAK
NIE
TAK
NIE
NIE

Note 1

On the first day, Bajtosia could have pointed at items 2, 1, 2, 3, 2 in sequence during the rhyme. On the third day, she used a short rhyme and started playing with the first toy pointed at. On the fifth day, she could have pointed at items 1, 2, 3, 4, 3, 2, 1, 2, 1 in sequence. For none of the other days does a suitable counting-out rhyme exist.