Шахматные доски
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, шахматные доски делают из коры крайне редкого хорватского шахматного дерева (Biggus Mobydiccus). Кору этого дерева сняли и развернули в огромный прямоугольный лист из черных и белых квадратов. Из этого листа на фабрике сделают несколько шахматных досок разного размера. Шахматной доской называется квадратный кусок коры со сторонами, параллельными сторонам прямоугольника, у которого никакие две соседние по стороне клетки не имеют одинаковый цвет.

Доски вырезают с помощью жадного алгоритма: каждый раз вырезаю максимальную по размеру шахматную доску, если есть несколько таких, выбирают самую верхний, а среди таких — самую левую. Доски вырезают, пока весь лист не кончится. Возможно, даже дойдет до того, что будут вырезаны нано-доски 1 × 1.

Вот пример, показывающий лист коры доска и первые семь шахматных досок, которые будут из него вырезаны.

Вам дано описание листа коры шахматного дерева. Посчитайте, сколько и каких досок получится из него в конце процесса.

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

Первая строка ввода содержит количество тестов t. Далее следуют описания t тестов. Каждый тест начинается со строки, содержащей размеры коры сетки, m и n, при этом n всегда кратна 4. Следующие m строк содержат строки по n / 4 символов — представления строк коры в шестнадцатеричном виде. Двоичное представление этих чисел даст вам строки из n бит, по одному для каждой строки. Нули обозначают черные квадраты, а единицы — белые квадраты. Строки заданы сверху вниз. В каждой строке, наиболее значимый бит шестнадцатеричного числа соответствует крайней слева ячейке этой строки.

Ограничения: 1 ≤ t ≤ 100, n делится на 4.

В задаче 1: 1 ≤ n, m ≤ 32.

В задаче 2: 1 ≤ n, m ≤ 512.

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

Для каждого теста выведите строку, содержащую число k — число различных размеров шахматной досок, которые будут вырезаны, следуя процедуре, описанной выше. Следующие k строк должны содержать по два целых числа — размер шахматной доски (от большего к меньшему) и количество шахматных досок такого размера, которые будут вырезаны.

Примеры тестов

Входные данные
4
15 20
55555
FFAAA
2AAD5
D552A
2AAD5
D542A
4AD4D
B52B2
52AAD
AD552
AA52D
AAAAA
5AA55
A55AA
5AA55
4 4
0
0
0
0
4 4
3
3
C
C
4 4
6
9
9
6
Выходные данные
5
6 2
4 3
3 7
2 15
1 57
1
1 16
2
2 1
1 12
1
2 4