玛丽亚终于得到了她梦寐以求的工作！她成为了天空之塔（Sky Tower）的一名专业夜间警卫。她的职责之一是报告大楼内的异常活动。幸运的是，她甚至不需要离开舒适的椅子就能完成工作。她所需要做的就是监控安装在摩天大楼里的摄像头。为此，她必须管理 $n$ 个不同的摄像头（编号为 $1$ 到 $n$）。她希望创建一个传输循环来处理来自摄像头的信息。她会观察某个摄像头的画面一分钟，然后切换到循环中的下一个摄像头。每个摄像头在循环中必须至少出现一次。还有一些额外的限制：在循环中，摄像头 $i$ 的任意两个相邻出现位置之间的距离不能超过 $a_i$。幸运的是，对于玛丽亚来说，对于任意 $1 \le i < j \le n$， $a_i$ 和 $a_j$ 中至少有一个是另一个的倍数。

如果可能的话，请帮助玛丽亚创建一个长度不超过 $10^6$ 的满足上述条件的循环。

输入格式

第一行包含一个整数 $Z \le 50$，表示接下来要描述的测试用例数量。

每个测试用例的第一行包含一个整数 $n$，表示天空之塔中的摄像头数量。

接下来的一行包含摄像头的描述。第 $i$ 个数字表示第 $i$ 个摄像头的参数 $a_i$。

$n \in [1, 10^5]$，$a_i \in [1, 10^5]$。

输出格式

对于每个测试用例：

如果无法构建这样的循环，输出的第一行（也是唯一一行）应包含单个单词 "NIE"。

如果可以构建这样的循环，第一行输出单个单词 "TAK"。下一行应包含对传输循环的描述。第一个数字 $m$ 表示循环的长度。接下来的 $m$ 个数字是循环中摄像头的编号，按它们在循环中出现的顺序排列。

如果有多个可能的答案，输出其中任意一个即可。

样例

输入样例 1

2
3
2 4 8
5
3 3 6 6 42

输出样例 1

TAK
4 1 2 1 3
NIE