Бурёнка пришла в детский сад. Этот детский сад очень странный, поэтому в нём каждому ребёнку дают две дроби (\(\frac{a}{b}\) и \(\frac{c}{d}\)), числители и знаменатели которых являются целыми числами, и заставляют играть с ними.
Бурёнка — умный ребёнок, поэтому она заметила, что за один хлопок в ладоши она может умножить числитель или знаменатель любой из двух своих дробей на любое целое число (но нельзя умножать знаменатели на \(0\)). Теперь она хочет сделать две дроби равными по значению за минимальное число хлопков. Помогите ей и сообщите это число!
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное число хлопков в ладоши, которое Бурёнке придётся сделать для того, чтобы сделать две дроби равными.
Примечание
В первом тестовом случае можно умножить \(c\) на \(2\), после этого дроби станут равными.
Во втором тестовом случае дроби уже равны.
В третьем тестовом случае можно умножить \(a\) на \(4\), а затем \(b\) на \(3\). Тогда дроби станут равны: \(\frac{1 \cdot 4}{2 \cdot 3} = \frac{2}{3}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
2 1 1 1
6 3 2 1
1 2 2 3
0 1 0 100
0 1 228 179
100 3 25 6
999999999 300000000 666666666 100000000
33 15 0 84
|
1
0
2
0
1
1
1
1
|