合作游戏由 $$$m$$$ 人玩。游戏中有 $$$3m$$$ 张纸:带有字母“w”的 $$$m$$$ 张纸、带有字母“i”的 $$$m$$$ 张纸和带有字母“n”的 $$$m$$$ 张纸。
最初,每个人都会收到三张纸(可能带有相同的字母)。
游戏的目标是让每个 $$$m$$$ 人用他们的纸拼写出“win”这个词。换句话说,每个人都应该有一张带有字母“w”的纸,一张带有字母“i”的纸,一张带有字母“n”的纸。
为了实现目标,人们可以进行交流。每次交流都有两个人参与。两人从自己拥有的三张纸中恰好选出一张并互相交换。
找到最短的交换序列,之后每个人都有一个“w”、一个“i”和一个“n”。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$m$$$ ($$$2 \le m \le 10^5$$$) — 人数。
接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含长度为 $$$3$$$ 的字符串 $$$s_i$$$,由小写英文字母“w”、“i”和“n”组成,表示游戏开始时 $$$i$$$ 在纸上的字母,顺序任意。
每个字母“w”、“i”和“n”在纸张上总共出现了 $$$m$$$ 次。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个非负整数 $$$k$$$ — 让每个人都有一个“w”、一个“i”和一个“n”所需的最少交换次数。
在接下来的 $$$k$$$ 行中,打印四个标记 $$$a_1$$$ $$$c_1$$$ $$$a_2$$$ $$$c_2$$$,按时间顺序描述交换 ($$$1 \le a_1, a_2 \le m$$$; $$$a_1 \ne a_2$$$; $$$c_1, c_2$$$ 是 $$$\{\mathtt{w}, \mathtt{i}, \mathtt{n}\}$$$ 之一:人 $$$a_1$$$ 将字母 $$$c_1$$$ 给予人 $$$a_2$$$,而人 $$$a_2$$$ 同时将字母 $$$c_2$$$ 给予人 $$$a_1$$$。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
3 2 nwi inw 3 inn nww wii 4 win www iii nnn
输出 #1
0 2 2 w 3 i 3 w 1 n 3 2 w 3 i 2 w 4 n 3 i 4 n