题目

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.

Sample Input

2 2 3 2 5

Sample Output

3 4

hint:

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

题解

把长方形按照一刀一刀切成正方形，最后求出所有正方形的个数

如图，2*3的长方形，第一刀可以分割成2*2的正方形和1*2的长方形；
第二刀可以分成两个1*1的正方形
即3个正方形

可以看出，对于一个n*m的长方形（n>m），其操作为分成m*m的正方形和(n-m)*m的长方形

提取出相同的操作，写成递归来统计个数

//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;
}