F. Знакомые операции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два целых положительных числа $$$a$$$ и $$$b$$$. С ними можно проводить следующие операции:

  1. умножить одно из чисел на некоторое простое число $$$p$$$;
  2. разделить одно из чисел на некоторое простое $$$p$$$, на которое оно делится.

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

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

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

В каждой из следующих $$$t$$$ строк содержатся два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^6$$$).

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

Выведите $$$t$$$ строк: в $$$i$$$-й из них должен содержаться ответ для пары $$$a_i$$$, $$$b_i$$$.

Пример
Входные данные
8
9 10
100 17
220 70
17 19
4 18
32 20
100 32
224 385
Выходные данные
1
3
1
0
1
0
1
1
Примечание

Числа с одинаковым количеством делителей, оптимальные для примера:

  • $$$(27, 10)$$$, 4 делителя
  • $$$(100, 1156)$$$, 9 делителей
  • $$$(220, 140)$$$, 12 делителей
  • $$$(17, 19)$$$, 2 делителя
  • $$$(12, 18)$$$, 6 делителей
  • $$$(50, 32)$$$, 6 делителей
  • $$$(224, 1925)$$$, 12 делителей

Обратите внимание, что может быть несколько оптимальных пар чисел.