Cossack Vus 和 Cossack Us 正在一个长度为 $n$、仅由数字 0-9 组成的字符串 $s$ 上玩游戏。

游戏双方轮流进行（Vus 先手），每次操作可以删除字符串 $s$ 中的任意一个字符。如果在游戏过程中的任意时刻，字符串中出现了两个相邻的相同字符，则 Us 获胜。如果所有字符都被删除了，且 Us 仍未获胜，则 Vus 获胜。

Cossack Vus 非常心急，甚至在游戏开始之前，他就想知道在双方都采取最优策略（即双方都为了获胜而玩游戏）的情况下，他是否能战胜 Us。他请求你帮他找出答案。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10$) —— 子测试的数量。

对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。

第二行包含一个长度为 $n$ 的字符串 $s$，仅由数字 0-9 组成。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行。如果 Cossack Vus 能获胜，输出 "Yes"；否则输出 "No"。

子任务

1. (8 分)：不同数字的数量 $\le 2$；
2. (8 分)：不同数字的数量 $\le 5$；
3. (6 分)：不同数字的数量 $\le 7$；
4. (8 分)：最多只有一个数字出现超过一次；
5. (7 分)：如果 $s_l = s_r$，$s_i = s_j$ 且 $s_i \ne s_l$（其中 $l \ne r$ 且 $i \ne j$），则区间 $[l, r]$ 和 $[i, j]$ 不重叠；
6. (7 分)：$n \le 4$；
7. (6 分)：$n \le 8$；
8. (6 分)：$n \le 12$；
9. (6 分)：$n \le 15$；
10. (38 分)：无附加限制。

上述限制适用于每个子测试。

样例

输入格式 1

4
6
015423
7
1235212
4
1111
6
156156

输出格式 1

Yes
Yes
No
No

说明

在第一个样例中，由于每个数字最多只出现一次，因此永远不会有两个相同的数字相邻。

在第二个样例中，Vus 可以先删除最后一个 2。之后，如果 Us 删除 1 或 2，Vus 分别对应删除 2 或 1，此时所有数字都变得互不相同，因此 Vus 必胜。然而，如果 Us 删除 3 或 5，那么 Vus 会先删除任意一个 2，然后再删除任意一个 1。

在第三个样例中，甚至在游戏开始之前，Us 就已经获胜了。