在 Bajtosia 的幼兒園裡有很多玩具，有時她很難決定當天要玩哪一個。為了方便選擇，Bajtosia 決定使用「數來寶」（一種用來決定的童謠遊戲）。

如果她在某一天想要從 $n$ 個玩具中選出一個，她會將它們全部排成一列，並從 $1$ 到 $n$ 編號。她從指向其中一個玩具開始，然後背誦數來寶，每唸一個音節，就移動到隊列中前一個或後一個玩具（在玩具 $1$ 和 $n$ 的情況下，她沒有選擇，必須分別移動到 $2$ 和 $n-1$）。最後一個被指到的玩具就是她當天要玩的玩具。

在數來寶的過程中，Bajtosia 會記錄每個玩具被指到的次數：數來寶結束後，第 $i$ 個玩具被指到了 $a_i$ 次。請檢查 Bajtosia 是否記錯了，也就是說，對於 Bajtosia 記錄的給定數列 $a_1, a_2, \dots, a_n$，判斷是否存在一種符合該數列的數來寶過程。

這種情況在 $t$ 天內重複發生，每天都有不同的玩具子集和不同的數來寶過程。

輸入格式

第一行包含一個整數 $t$ ($1 \le t \le 100\,000$)，表示 Bajtosia 使用數來寶選擇玩具的天數。接下來是 $t$ 個關於每一天的描述，依序排列。

每一天的描述中，第一行包含一個整數 $n$ ($1 \le n \le 1\,000\,000$)，表示當天參與數來寶的玩具數量。第二行包含一個由 $n$ 個整數組成的數列 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示根據 Bajtosia 的記錄，各個玩具在數來寶過程中被指到的次數。

你可以假設至少有一個 $a_i$ 是非零的。

所有 $t$ 天的 $n$ 值總和不超過 $1\,000\,000$。

輸出格式

輸出 $t$ 行，每行包含一個單詞 TAK 或 NIE。單詞 TAK 表示存在符合 Bajtosia 記錄數列的數來寶過程，單詞 NIE 表示不存在這樣的數來寶過程。

範例

範例輸入 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

第一天，Bajtosia 在數來寶過程中可能依序指到了玩具 2, 1, 2, 3, 2。 第三天，她使用了簡短的數來寶，並開始玩第一個被指到的玩具。 而第五天，她可能依序指到了玩具 1, 2, 3, 4, 3, 2, 1, 2, 1。 對於其餘的日子，不存在對應的數來寶過程。