Pinot

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		if (a == b) {
			cout << 1 << endl;
			continue;
		}
		int c = 0;
		while (a != 0 && b != 0) {
			if (a < b) {
				int c = a;
				a = b;
				b = c;
			}
			int diff = a - b;
			if (diff < b) {
				a -= b;
				c++;
			}
			else {
				int t = diff / b;
				c += t;
				a -= b * t;
			}
		}
		cout << c << endl;
	}

	return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED