埃及终于在 1990 年之后再次打进了世界杯！

在世界杯中，球队被分成若干小组，每组 4 支球队。但在本题中，我们将推广这一规则，假设小组共有 $N$ 支球队（编号从 1 到 $N$），我们将模拟仅包含一个小组的比赛。以下是小组赛的规则（与实际规则略有不同）：

1. 小组赛共进行 $N-1$ 轮，每轮有 $N/2$ 场比赛（本题保证 $N$ 为偶数）。
2. 每支球队在每一轮中进行一场比赛，且每对不同的球队在 $N-1$ 轮中恰好交手一次（即每支球队与其他 $N-1$ 支球队各交手一次）。
3. 在每场比赛中，胜者积 3 分，负者积 0 分；若平局，则双方各积 1 分。
4. 在 $N-1$ 轮比赛结束后，计算每支球队的总积分，积分最高的前 2 名球队将晋级下一阶段（注意，即使 $N$ 大于 4，也始终是前 2 名晋级）。
5. 所有与前 2 名积分相同的球队也将晋级（本题不考虑净胜球等其他因素）。这意味着如果所有球队积分相同，则整个小组的所有球队都可能晋级。

给定一个小组前 $N-2$ 轮的比赛结果，你的任务是计算每支球队是否还有机会晋级下一轮，或者无论最后一轮结果如何都已被淘汰。

输入格式

程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行是一个整数 $N$ ($4 \le N \le 1,000$)，表示球队数量。接下来有 $(N-2) \times (N/2)$ 行，每行是一场比赛的结果。

每行比赛结果以两个空格分隔的整数 $A$ 和 $B$ 开头 ($1 \le A < B \le N$)，随后是一个空格和一个字符，字符为 'W'（表示球队 $A$ 获胜）、'L'（表示球队 $B$ 获胜）或 'D'（表示平局）。

在每个测试用例中，保证每支球队恰好参加了 $N-2$ 场比赛，且没有一对球队交手超过一次。

输出格式

对于每个测试用例，打印一行包含 $N$ 个字符的字符串，第一个字符对应球队 1，第二个字符对应球队 2，以此类推。如果对应的球队还有机会晋级下一轮，则字符应为 '1'；如果球队无论如何都已被淘汰，则字符应为 '0'。

样例

输入 1

2
4
1 2 W
3 4 W
1 4 W
2 3 L
6
1 2 D
1 3 D
1 4 D
1 5 D
2 3 D
2 4 D
2 6 D
3 5 D
3 6 D
4 5 D
4 6 D
5 6 D

输出 1

1010
111111

说明

在第一个测试用例中，球队 1 和 3 目前积 6 分，球队 2 和 4 积 0 分。无论最后一轮发生什么，球队 2 和 4 都不可能进入前 2 名。

在第二个测试用例中，所有比赛都以平局结束，因此所有球队都还有机会晋级。