Bituś 和 Bajtuś 正在 Bajtockie 海度假。但即使在沙滩上，比起温暖的沙子和高高的海浪，他们更感兴趣的是智力娱乐。他们收集了一大堆海浪冲上岸的圆形小石子，并开始了一种新游戏。规则非常简单。Bituś 在第一步可以拿走任意非零数量的石子，前提是不拿走全部。接下来，两个男孩（从 Bajtuś 开始）轮流行动，在每一步中，他们可以拿走之前 没有被拿走过 的任意非零数量的石子（包括拿走整个剩余的堆）。换句话说，每一步都必须拿走不同数量的石子。不能行动的一方输掉游戏。

现在给定游戏开始时的石子数量，并假设两个男孩都以最优策略进行游戏，请判断 Bituś 是否会赢得游戏。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 1\,000\,000$），表示需要考虑的测试用例数量。

接下来的 $t$ 行中，每行包含一个整数 $n$（$1 \le n \le 1\,000\,000\,000$），表示游戏开始时的石子数量。

输出格式

输出应包含恰好 $t$ 行，对应于输入中的每个测试用例的答案。每行应输出一个单词 TAK 或 NIE，表示 Bituś 是否会赢得游戏。

示例

输入

1
3

输出

NIE