# 题目

## Description

It is the king's birthday before the military parade . The ministers prepared a rectangle cake of size n \times m(1\le n, m \le 10000)2×22×2

## Input

The first line contains a number T(T \leq 1000), the number of the testcases.

For each testcase, the first line and the only line contains two positive numbers n , m(1\le n, m \le 10000)1×11×1

## Output

For each testcase, print a single number as the answer.

2 2 3 2 5

3 4

## hint:

For the first testcase you can divide the into one cake of , 2 cakes of

# 题解

//a长 b宽
int DFS(int a, int b) {
if (a == b)
return 1;
return 1 + DFS(max(a - b, b), min(a - b, b));

}


# 代码

/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい？
エリーチカ！

*/
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

//a长 b宽
int DFS(int a, int b) {
if (a == b)
return 1;
return 1 + DFS(max(a - b, b), min(a - b, b));

}

void Do() {
int n, m;
scanf("%d%d", &n, &m);
printf("%d\n", DFS(max(m, n), min(m, n)));
}

int main() {
int T;
scanf("%d", &T);
while (T--)
Do();
return 0;
}