通用人工智能（Artificial General Intelligence，简称 AGI）似乎正变得越来越不可避免。越来越多的人不再询问我们是否会达到这一水平，而是询问何时会达到。到目前为止，已有 $n$ 位未来学家给出了关于 AGI 何时会出现的预测。第 $i$ 个预测给出的时间区间为 $[A_i, B_i)$，这意味着根据该预测，AGI 将在满足 $A_i \le t < B_i$ 的时间 $t$ 出现。

对于每一个预测，你必须决定你是否认为它是正确的。

你的任务是做出这些决定，使得无论 AGI 最终出现的实际时刻 $x$ 是多少，你都能保证至少有 $\lfloor \frac{n-1}{2} \rfloor$ 个评估是正确的。

你可以假设测试用例的选择保证了至少存在一个有效的答案。你需要解决 $t$ 个独立的测试用例。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。每个测试用例包含一行整数 $n$ ($1 \le n \le 500\,000$)，表示预测的数量，随后是 $n$ 行描述预测的内容，每行包含两个整数 $A_i$ 和 $B_i$ ($0 \le A_i < B_i \le 10^9$)，分别表示第 $i$ 个预测的时间区间的开始和结束。

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

输出格式

对于每个测试用例，输出一行长度为 $n$ 的字符串，由字母 T 和 N 组成。字符串的第 $j$ 个字符表示你对第 $j$ 个预测的评估：

• T 表示你肯定该预测。
• N 表示你否定该预测。

如果存在多个满足题目要求的答案，你可以输出其中任意一个。

样例

输入 1

2
4
1 2
2 3
3 4
4 5
5
1 10
2 9
3 8
4 7
5 6

输出 1

NNNN
TNTNN

说明

在第一个测试用例中，只需正确评估至少 $\lfloor \frac{4-1}{2} \rfloor = 1$ 个预测即可。所有区间的交集为空，因此通过否定所有预测，我们至少能正确评估一个。

在第二个测试用例中，我们必须正确评估至少 $\lfloor \frac{5-1}{2} \rfloor = 2$ 个预测。例如，如果 AGI 在时间 $x = 2$ 出现，那么预测 1 和 2 将为真，因此我们正确评估了预测 1、4、5。如果 AGI 在 $x = 5.7$ 时出现，那么所有预测都为真，因此我们仅正确评估了预测 1、3，这仍然是足够的。可以证明，无论 $x$ 为何值，至少有 2 个预测会被正确评估。