Formula One

Little Bytie loves watching the Formula One races held every year on the track between Bytetown and Byteburg. What thrills him most are the overtakes, and he would like to see as many of them as possible.

Bytie imagines a race with $n$ cars in which the car that starts in the $i$-th position (for each $1 \le i \le n$) performs exactly $a_i$ overtakes during the race. For simplicity, assume that at any moment at most one overtake takes place, and that it involves exactly two cars (one car passes another).

Help Bytie decide whether such a race is possible at all.

The first line contains one integer $t$, the number of test cases that follow.

Each test case is described by two lines. The first line contains one integer $n$ ($1 \le n \le 1\,000\,000$), the number of cars in the race. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), where $a_i$ is the number of overtakes made by the car that started in the $i$-th position.

The total size of a single input file does not exceed 20 MB.

For each test case output one line containing the single word TAK ("yes" in Polish) if the described race is possible, or NIE ("no" in Polish) if it is not.