2410 - Nim游戏

     一排n个格子，两人轮流用k种颜色给未染色的格子染色，要求每次染色后都不能有两个相邻的格子被染上了相同的颜色，你需要做的是判断一个已有部分格子被染色的初始局面是先手必胜还是后手必胜。

Input

   第一行一个数time，表示数据组数。
   接下来每组数据的第一行两个数n，k如题中所述，第二行n个0到k的整数，0表示格子未染色，否则表示该格子的颜色。
   保证初始局面没有两个相邻格子同色。

Output

   共time行，每行为“y”表示先手必胜，“n”表示后手必胜。

Examples

Input

NG.in 
2 
5 2 
0 0 1 0 0
5 1
1 0 0 0 0

Output

n
y

Hint

第一局游戏中局面是对称的，所以只要先手可以给格子染色，后手就可以给其对称的格子染色，故后手必胜。

   第二局游戏中，先手给第4个格子染色后，后手就不能染色了，故先手必胜。

对于100%的数据 1≤n≤105

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题