В детском саду у Байтоси много игрушек, и иногда девочке трудно решить, с какой из них она будет играть в данный день. Чтобы облегчить выбор, Байтося решила использовать считалочки.

Если в какой-то день она хочет выбрать одну из $n$ игрушек, она расставляет их все в ряд и нумерует от $1$ до $n$. Она начинает с того, что указывает на одну из игрушек, а затем произносит считалочку, при каждом слоге переходя к предыдущей или следующей игрушке в ряду (в случае игрушек $1$ и $n$ выбора нет, и она должна перейти, соответственно, к $2$ и $n - 1$). Последней выбранной игрушкой она играет остаток дня.

Во время считалочки Байтося отслеживает, сколько раз она указывает на каждую из игрушек: после окончания считалочки $i$-я игрушка была указана $a_i$ раз. Проверьте, не ошиблась ли Байтося, то есть для данной последовательности $a_1, a_2, \dots, a_n$, запомненной Байтосей, определите, существует ли считалочка, соответствующая ей.

Эта ситуация повторялась в течение $t$ дней с разными наборами игрушек и разными считалочками.

Входные данные

Первая строка содержит целое число $t$ ($1 \le t \le 100\,000$), обозначающее количество дней, в которые Байтося использовала считалочки для выбора игрушки. Далее следуют $t$ описаний для каждого дня, одно за другим.

Первая строка описания дня содержит одно целое число $n$ ($1 \le n \le 1\,000\,000$), обозначающее количество игрушек, участвующих в считалочке в этот день. Вторая строка содержит последовательность из $n$ целых чисел $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), обозначающих, сколько раз, по мнению Байтоси, были указаны соответствующие игрушки во время считалочки.

Вы можете предположить, что хотя бы одно из чисел $a_i$ не равно нулю.

Сумма всех значений $n$ по всем $t$ дням не превышает $1\,000\,000$.

Выходные данные

Выведите $t$ строк, каждая из которых содержит одно из слов TAK или NIE. Слово TAK означает, что существует считалочка, соответствующая последовательности, запомненной Байтосей, а слово 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

Пример 2

TAK
NIE
TAK
NIE
TAK
NIE
NIE

Примечание

Пояснение к примеру: В первый день Байтося во время считалочки могла указывать последовательно на предметы $2, 1, 2, 3, 2$. В третий день она использовала короткую считалочку и начала играть с первой указанной игрушкой. В пятый день она могла указывать последовательно на предметы $1, 2, 3, 4, 3, 2, 1, 2, 1$. Ни для одного из остальных дней подходящей считалочки не существует.