n = int(input())
for i in range(n):
(a, b) = map(int, input().split(' '))
if max(a, b) % min(a, b) == 0:
print(max(a, b) // min(a, b))
else:
operations = 0
bigger_number = max(a, b)
smaller_number = min(a, b)
while bigger_number != smaller_number:
if bigger_number < smaller_number:
smaller_number, bigger_number = bigger_number, smaller_number
if bigger_number % smaller_number == 0:
operations += (bigger_number - smaller_number) // smaller_number
break
else:
operations += bigger_number // smaller_number
bigger_number = bigger_number % smaller_number
print(operations + 1)
#include <cstdio>
int main(){
int n; scanf("%d", &n);
while(n--){
long a(0), b(0); scanf("%ld %ld", &a, &b);
long total(0);
while(a > 0 && b > 0){
if(a > b){total += a/b; a -= (a/b) * b;}
else{total += b/a; b -= (b/a) * a;}
}
printf("%ld\n", total);
}
return 0;
}688B - Lovely Palindromes | 66B - Petya and Countryside |
1557B - Moamen and k-subarrays | 540A - Combination Lock |
1553C - Penalty | 1474E - What Is It |
1335B - Construct the String | 1004B - Sonya and Exhibition |
1397A - Juggling Letters | 985C - Liebig's Barrels |
115A - Party | 746B - Decoding |
1424G - Years | 1663A - Who Tested |
1073B - Vasya and Books | 195B - After Training |
455A - Boredom | 1099A - Snowball |
1651D - Nearest Excluded Points | 599A - Patrick and Shopping |
237A - Free Cash | 1615B - And It's Non-Zero |
1619E - MEX and Increments | 34B - Sale |
1436A - Reorder | 1363C - Game On Leaves |
1373C - Pluses and Minuses | 1173B - Nauuo and Chess |
318B - Strings of Power | 1625A - Ancient Civilization |