一个整数区间 $[1, L]$ 被拆分为 $N$ 个非空整数区间 $[a_i, b_i]$ ($1 \le a_i \le b_i \le L$, 对于 $1 \le i \le N$)，使得 $[1, L]$ 中的每个整数恰好属于其中一个区间 $[a_i, b_i]$。随后，这些所得区间 $[a_i, b_i]$ 的部分边界被隐藏了。

给定一组区间，其中一些边界可能缺失。你的任务是判断它们是否可能由上述方法产生，即是否存在一种方式替换缺失的值，使得这些区间非空、两两不相交，且共同覆盖了从 $1$ 到 $L$ 的所有整数。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 30\,000$)，表示测试用例的数量。 接下来是 $T$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $N$ 和 $L$ ($1 \le N \le 200\,000$, $1 \le L \le 10^9$)，分别表示给定区间的数量和原始区间的长度。接下来的 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($-1 \le a_i, b_i \le L$; $a_i, b_i \neq 0$)。数字 $-1$ 表示缺失的值。如果两个数字 $a_i$ 和 $b_i$ 均为正数，则满足 $a_i \le b_i$。

所有测试用例中 $N$ 的总和不超过 $200\,000$。

输出格式

输出应包含恰好 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案：如果输入的区间可以通过题目描述的方法生成，则输出单词 TAK，否则输出单词 NIE。

样例

样例输入 1

3
4 51
1 -1
11 50
-1 -1
-1 10
3 2
-1 -1
-1 -1
-1 -1
2 3
1 2
2 3

样例输出 1

TAK
NIE
NIE

说明

在第一个测试用例中，$L = 51$，区间 $[1, 51]$ 可以被拆分为例如 $[1, 7]$、$[8, 10]$、$[11, 50]$ 和 $[51, 51]$。在隐藏部分值后，这些区间与给定的区间 $[1, -1]$、$[-1, 10]$、$[11, 50]$ 和 $[-1, -1]$ 相匹配。因此，该测试用例的答案为 TAK。

在第二个测试用例中，我们有 $3$ 个区间，所有区间的边界都被隐藏了。然而，区间 $[1, 2]$ 仅包含两个整数，因此不可能将其拆分为 $3$ 个非空且不相交的整数区间。因此，该测试用例的答案为 NIE。

在第三个测试用例中，我们有两个没有缺失边界的区间 $[1, 2]$ 和 $[2, 3]$。数字 $2$ 被覆盖了两次，因此答案为 NIE。