У вас есть два положительных целых числа \(a\) и \(b\).
Вы можете выполнять операции двух видов:
Найдите минимальное количество операций, которое нужно, чтобы сделать \(a=0\).
В первой строке находится единственное целое число \(t\) (\(1 \le t \le 100\)) — количество наборов входных данных.
В единственной строке описания каждого набора входных данных находится два целых числа \(a\), \(b\) (\(1 \le a,b \le 10^9\)).
Для каждого набора входных данных выведите единственное целое число: минимальное количество операций, которое нужно, чтобы сделать \(a=0\).
В первом наборе входных данных одно из оптимальных решений — следующее.
6 9 2 1337 1 1 1 50000000 4 991026972 997 1234 5678
4 9 2 12 3 1
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач