Bajtosiの幼稚園にはたくさんのおもちゃがあり、彼女は毎日どのおもちゃで遊ぶか決めるのに苦労することがあります。選択を簡単にするために、Bajtosiは数え歌を使うことにしました。

ある日、$n$ 個のおもちゃの中から1つを選びたいとき、彼女はそれらすべてを一列に並べ、$1$ から $n$ まで番号を振ります。彼女はまずいずれかのおもちゃを指差し、それから数え歌を唱えながら、音節ごとに列の隣のおもちゃ（左または右）へ移動します（$1$ 番目のおもちゃと $n$ 番目のおもちゃにいるときは、それぞれ $2$ 番目と $n-1$ 番目へ移動するしかありません）。最後に指差したおもちゃで、その日の残りの時間を遊びます。

Bajtosiは数え歌の間に、それぞれのおもちゃを何回指差したかを記録しています。数え歌が終わったとき、$i$ 番目のおもちゃは $a_i$ 回指差されました。Bajtosiが記録した数列 $a_1, a_2, \dots, a_n$ に対して、それに適合する数え歌が存在するかどうかを判定してください。

この状況は $t$ 日間繰り返され、毎日異なるおもちゃの集合と異なる数え歌が使われました。

入力

最初の行には、Bajtosiがおもちゃを選ぶために数え歌を使用した日数 $t$ ($1 \le t \le 100\,000$) が含まれます。続いて、$t$ 日分の日ごとの記述が順に続きます。

各日の記述の最初の行には、その日に数え歌に参加したおもちゃの数 $n$ ($1 \le n \le 1\,000\,000$) が含まれます。2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) が含まれ、Bajtosiの記録に従って各おもちゃが指差された回数を表します。

少なくとも1つの $a_i$ が $0$ でないことを仮定して構いません。

すべての $t$ 日間における $n$ の合計は $1\,000\,000$ を超えません。

出力

Bajtosiが記録した数列に適合する数え歌が存在する場合は TAK を、存在しない場合は NIE を、それぞれ $t$ 行にわたって出力してください。

入出力例

入力 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

出力 1

TAK
NIE
TAK
NIE
TAK
NIE
NIE

注記

例の解説： 1日目、Bajtosiは数え歌の間に順に $2, 1, 2, 3, 2$ 番目のおもちゃを指差した可能性があります。 3日目、彼女は短い数え歌を使い、最初に指差したおもちゃで遊び始めました。 5日目、彼女は順に $1, 2, 3, 4, 3, 2, 1, 2, 1$ 番目のおもちゃを指差した可能性があります。 残りの日については、適切な数え歌は存在しません。