棋盘游戏

题目描述

有一个100 * 100的棋盘，其中左下角的编号为(0, 0), 右上角编号为(99, 99)。棋盘上有N个Queen，最开始第i个Queen的位置为(Xi, Yi)。现在有两个玩家依次来操作，每一次一个玩家可以选择其中一个Queen，将它跳到(Xi – k, Yi)或(Xi, Yi - k)或(Xi – k, Yi - k), 其中k > 0。注意在游戏的过程中，一个格子里面可能出现多个Queen。如果谁先将任意一个Queen移动到(0, 0), 谁就获胜。问先手必胜还是后手必胜?

---

输入格式

注意本题是多组数据。 第一行有一个数T, 表示数据组数。 接下来有T组数据，每组数据的第一行一个正整数N表示Queen的个数。接下来N行每行两个数表示第i个Queen的初始位置Xi, Yi(0 <= Xi <= 99, 0 <= Yi <= 99)。

---

输出格式

对于每一组数据，你需要输出是先手必胜还是后手必胜。 如果是先手必胜，输出“^o^“, 如果是后手必胜，输出”T_T”。

---

样例输入

2
2
3 4
3 5
3
3 2
4 2
3 1

---

样例输出

^o^
T_T
数据范围
T <= 10, N <= 1000

---

提示

没有写明提示

---

题目来源

没有写明来源