B. Обмен буквами
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В кооперативную игру играют $$$m$$$ человек. В игре есть $$$3m$$$ листков бумаги: $$$m$$$ листков с буквой «w», $$$m$$$ листков с буквой «i» и $$$m$$$ листков с буквой «n».

Изначально каждому игроку дают три листка (возможно, с одинаковыми буквами).

Цель игры — сделать так, чтобы каждый из $$$m$$$ человек мог сложить из своих листков бумаги слово «win». Другими словами, у каждого игрока должен оказаться один листок с буквой «w», один листок с буквой «i» и один листок с буквой «n».

Чтобы достичь цели, игроки могут производить обмены. В каждом обмене участвуют два игрока. Каждый из них выбирает ровно один из своих листков бумаги, и потом игроки обмениваются выбранными листками.

Найдите кратчайшую последовательность обменов, после которой у каждого игрока будет одна буква «w», одна буква «i» и одна буква «n».

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$m$$$ ($$$2 \le m \le 10^5$$$) — число игроков.

$$$i$$$-я из следующих $$$m$$$ строк содержит строку $$$s_i$$$ длины $$$3$$$, состоящую из строчных латинских букв «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$$$.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
3
2
nwi
inw
3
inn
nww
wii
4
win
www
iii
nnn
Выходные данные
0
2
2 w 3 i
3 w 1 n
3
2 w 3 i
2 w 4 n
3 i 4 n