Даны два целых положительных числа \(a\) и \(b\). С ними можно проводить следующие операции:
- умножить одно из чисел на некоторое простое число \(p\);
- разделить одно из чисел на некоторое простое \(p\), на которое оно делится.
Какое наименьшее число операций надо сделать, чтобы получились два числа, у которых совпадает число делителей? Вам дано несколько таких пар чисел, вам нужно вычислить ответ для каждой такой пары.
Выходные данные
Выведите \(t\) строк: в \(i\)-й из них должен содержаться ответ для пары \(a_i\), \(b_i\).
Примечание
Числа с одинаковым количеством делителей, оптимальные для примера:
- \((27, 10)\), 4 делителя
- \((100, 1156)\), 9 делителей
- \((220, 140)\), 12 делителей
- \((17, 19)\), 2 делителя
- \((12, 18)\), 6 делителей
- \((50, 32)\), 6 делителей
- \((224, 1925)\), 12 делителей
Обратите внимание, что может быть несколько оптимальных пар чисел.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|