E. Таблица и делители
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана таблица умножения $$$n \times n$$$ и положительное целое число $$$m = m_1 \cdot m_2$$$. Таблица умножения $$$n \times n$$$ — это таблица из $$$n$$$ строк и $$$n$$$ столбцов, пронумерованных от $$$1$$$ по $$$n$$$, где $$$a_{i, j} = i \cdot j$$$.

Для каждого делителя $$$d$$$ числа $$$m$$$ определите: встречается ли $$$d$$$ в таблице хотя бы раз, и если встречается, то какой наименьший номер строки, которая содержит $$$d$$$.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных.

В первой и единственной строке каждого набора заданы три целых числа $$$n$$$, $$$m_1$$$ и $$$m_2$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le m_1, m_2 \le 10^9$$$) — размер таблицы умножения и число $$$m$$$, представленное как $$$m_1 \cdot m_2$$$.

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

Для каждого набора входных данный, пусть $$$d_1, d_2, \dots, d_k$$$ – это все делители $$$m$$$, отсортированные в порядке возрастания. А также, пусть $$$a_1, a_2, \dots, a_k$$$ — это массив ответов, где $$$a_i$$$ равно наименьшему номеру строки, в которой встречается $$$d_i$$$, либо $$$0$$$, если такой строки в таблице нет.

Так как массив $$$a$$$ может быть длинным, выведите сначала число $$$s$$$ — количество делителей $$$m$$$, которые встречаются в таблице умножения $$$n \times n$$$. Далее выведите одно число $$$X = a_1 \oplus a_2 \oplus \dots \oplus a_k$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Пример
Входные данные
3
3 72 1
10 10 15
6 1 210
Выходные данные
6 2
10 0
8 5
Примечание

В первом наборе входных данных, $$$m = 72 \cdot 1 = 72$$$ и имеет $$$12$$$ делителей $$$[1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]$$$. Таблица умножения $$$3 \times 3$$$ выглядит следующим образом:

123
1123
2246
3369

Для каждого делителя $$$m$$$, что присутствует в таблице, выделена позиция с наименьшим номером строки. Соответственно, массив ответов $$$a$$$ равен $$$[1, 1, 1, 2, 2, 0, 3, 0, 0, 0, 0, 0]$$$. В нем только $$$6$$$ ненулевых значений, а исключающее ИЛИ $$$a$$$ равен $$$2$$$.

Во втором наборе, $$$m = 10 \cdot 15 = 150$$$ и имеет $$$12$$$ делителей $$$[1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150]$$$. Все делители кроме $$$75$$$ и $$$150$$$ присутствуют в таблице $$$10 \times 10$$$. Массив $$$a$$$ $$$=$$$ $$$[1, 1, 1, 1, 1, 1, 3, 5, 3, 5, 0, 0]$$$. В нем $$$10$$$ ненулевых значений и исключающее ИЛИ $$$a$$$ равно $$$0$$$.

В третьем наборе, $$$m = 1 \cdot 210 = 210$$$ и имеет $$$16$$$ делителей $$$[1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210]$$$. Таблица умножения $$$6 \times 6$$$ с выделенными делителями изображена ниже:

123456
1123456
224681012
3369121518
44812162024
551015202530
661218243036

Массив $$$a$$$ $$$=$$$ $$$[1, 1, 1, 1, 1, 0, 2, 0, 3, 0, 5, 0, 0, 0, 0, 0]$$$. В нем $$$8$$$ ненулевых значений и исключающее ИЛИ $$$a$$$ равно $$$5$$$.