在遥远的 Googlia 岛上，有两个城市：Truthtown 和 Liarville。来自 Truthtown 的人总是说真话，而来自 Liarville 的人总是说谎。在探索 Googlia 时，你遇到了由 N 个居民组成的一个群体，你想弄清楚每个人来自哪个城市。

为了简化问题，你首先将这些人从 1 到 N 进行编号。然后你询问每个人，并用下面描述的简写形式记录他们的 M 条陈述。

你的任务是推断出每个人来自哪个城市。保证至少存在一个解。

例如，假设你得到了以下陈述：

1 D 2 3，1 D 2 4，1 D 3 4 和 2 L 1。

那么，你可以进行如下推理：

• 只有两个城市，所以居民 #2、#3 和 #4 不可能都来自不同的城市。
• 因此，居民 #1 的陈述中至少有一个是谎言。
• 因此，居民 #1 来自 Liarville，并且他的所有陈述都必须是谎言。
• 因此，居民 #2、#3 和 #4 必须都来自同一个城市。
• 居民 #2 的陈述是真的，所以他必须来自 Truthtown。
• 因此，居民 #3 和 #4 也来自 Truthtown。

输入格式

输入的第一行给出测试用例的数量 T。接下来是 T 个测试用例。每个用例以包含整数 N 和 M 的一行开始。接下来的 M 行每行包含来自一个居民的一条陈述，格式如上所述。

输出格式

对于每个测试用例，输出一行，包含 "Case #x: y₁ y₂ ... y_N"，其中 x 是用例编号（从 1 开始），y_i 是一个字母，表示居民 #i 来自哪个城市：

• 如果给定的陈述暗示居民 #i 必须来自 Truthtown，则 y_i 应为 'T'。
• 如果给定的陈述暗示居民 #i 必须来自 Liarville，则 y_i 应为 'L'。
• 如果给定的陈述不足以确定居民 #i 来自哪里，则 y_i 应为 '-'。

数据范围

• 1 ≤ T ≤ 100
• 1 ≤ i, j, k ≤ N
• j 和 k 互不相同

小数据集 (12 分)

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ 500

小数据集 (23 分)

• 1 ≤ N ≤ 500
• 1 ≤ M ≤ 500

样例

输入样例 1

2
4 4
1 D 2 3
1 D 2 4
1 D 3 4
2 L 1
3 1
1 S 1 2

输出样例 1

Case #1: L T T T
Case #2: - T -