Bytemommy 全心全意地爱着她的 Bytekids。然而她有点健忘，所以她没有给他们起正式的名字，而是用从 $1$ 到 $n$ 的连续整数给他们编号。每天她都会为每个 Bytekid 在他们最喜欢的杯子里准备茶。他们家所有茶杯的一个奇特属性是，尽管它们只占用有限的空间，但它们拥有无限的容量。不过，这只是为了简化问题。第 $i$ 个 Bytekid 每天喜欢喝正好 $l_i$ bitres 的茶。然而，茶的量并不是他们唯一的追求——茶的温度也必须经过适当的调节。第 $i$ 个 Bytekid 希望他的茶正好是 $b_i$ Bytesius 度。

不幸的是，有一天，粗心的 Bytemommy 把茶的温度弄乱了，第 $i$ 个杯子里的茶温度正好是 $a_i$ Bytesius 度，而不是 $b_i$（不过第 $i$ 个孩子杯子里仍然有 $l_i$ bitres 的茶）。现在一切还来得及——Bytekids 非常聪明，他们利用一些辅助杯子开始混合他们的茶，试图得到具有合适茶量和温度的杯子。你需要确定 Bytekids 是否有可能达到他们的目标，即得到 $n$ 杯茶，使得第 $i$ 杯茶正好有 $l_i$ bitres 和 $b_i$ Bytesius 度。

形式上，Bytekids 被允许任意多次执行以下步骤：

• 分割茶：给定一个有 $a$ bitres 温度为 $t$ 的茶杯，创建两个茶杯，分别有 $x$ 和 $a - x$ bitres 温度为 $t$ 的茶，其中 $x$ 为任意实数且满足 $0 < x < a$（显然，初始的茶杯将不再存在）。
• 混合茶：给定两个分别有 $a$ 和 $b$ bitres 温度为 $t_a$ 和 $t_b$ 的茶杯，创建一个有 $a + b$ bitres 温度为 $$\frac{a \cdot t_a + b \cdot t_b}{a + b}$$ 的茶杯，即初始温度的加权平均值（同样，初始的两个茶杯将不再存在）。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 100\,000$)，表示测试用例的数量。 每个测试用例的描述以一行包含一个整数 $n$ ($1 \le n \le 100\,000$) 开始，表示 Bytekids 的数量。接下来的 $n$ 行描述 Bytekids：第 $i$ 行包含三个整数 $l_i, a_i$ 和 $b_i$ ($1 \le l_i, a_i, b_i \le 1\,000\,000$)，分别表示第 $i$ 个杯子中茶的量（初始量和最终所需量相同）以及该茶的初始温度和所需温度。 所有测试用例的 $n$ 之和不超过 $1\,000\,000$。

输出格式

你需要打印 $t$ 行，如果第 $i$ 个测试用例中 Bytekids 有可能达到他们的目标，则第 $i$ 行应包含单词 TAK，否则输出 NIE。

样例

输入 1

5
2
2 1 4
2 5 2
2
1 4 3
1 5 4
2
1 5 7
1 7 5
2
1 4 1
1 2 5
3
2 6 4
1 2 3
3 4 5

输出 1

TAK
NIE
TAK
NIE
TAK

说明 1

将茶杯表示为数字对。对 $(l, t)$ 表示一个有 $l$ bitres 温度为 $t$ Bytesius 度的茶杯。

在第一个测试用例中，Bytekids 有杯子 $(2, 1)$ 和 $(2, 5)$。通过分割茶的操作，他们可以得到杯子 $(\frac{1}{2}, 1), (\frac{3}{2}, 1), (\frac{1}{2}, 5)$ 和 $(\frac{3}{2}, 5)$。然后，通过混合杯子 $(\frac{1}{2}, 1)$ 和 $(\frac{3}{2}, 5)$，他们得到 $\frac{1}{2} + \frac{3}{2} = 2$ bitres 的茶，温度为 $$\frac{\frac{1}{2} \cdot 1 + \frac{3}{2} \cdot 5}{\frac{1}{2} + \frac{3}{2}} = 4$$ 即杯子 $(2, 4)$。类似地，通过混合杯子 $(\frac{3}{2}, 1)$ 和 $(\frac{1}{2}, 5)$，他们得到 $(2, 2)$。最后，Bytekids 将拥有两个具有合适茶量和温度的杯子。

在第二个测试用例中，两杯茶都太热了。我们在这里做不了太多事情。

然而，在第三个测试用例中，Bytekids 只需要交换他们的杯子即可。