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) b -= a;
			else a -= b;
			c++;
		}

		cout << c << endl;
		
	}

	return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED