A. Бурёнка играет с дробями
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бурёнка пришла в детский сад. Этот детский сад очень странный, поэтому в нём каждому ребёнку дают две дроби ($$$\frac{a}{b}$$$ и $$$\frac{c}{d}$$$), числители и знаменатели которых являются целыми числами, и заставляют играть с ними.

Бурёнка — умный ребёнок, поэтому она заметила, что за один хлопок в ладоши она может умножить числитель или знаменатель любой из двух своих дробей на любое целое число (но нельзя умножать знаменатели на $$$0$$$). Теперь она хочет сделать две дроби равными по значению за минимальное число хлопков. Помогите ей и сообщите это число!

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит четыре целых числа $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$ ($$$0 \leq a, c \leq 10^9$$$, $$$1 \leq b, d \leq 10^9$$$) — числители и знаменатели дробей.

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

Для каждого набора входных данных выведите единственное число — минимальное число хлопков в ладоши, которое Бурёнке придётся сделать для того, чтобы сделать две дроби равными.

Пример
Входные данные
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
Примечание

В первом тестовом случае можно умножить $$$c$$$ на $$$2$$$, после этого дроби станут равными.

Во втором тестовом случае дроби уже равны.

В третьем тестовом случае можно умножить $$$a$$$ на $$$4$$$, а затем $$$b$$$ на $$$3$$$. Тогда дроби станут равны: $$$\frac{1 \cdot 4}{2 \cdot 3} = \frac{2}{3}$$$.