Contents

1. 1. 问题描述
2. 2. 输入描述
3. 3. 输出描述
4. 4. 输入样例
5. 5. 输出样例
6. 6. Hint
7. 7. 不需要考虑一开始输入的a就一定要大于b，因为如果a

问题描述

阅兵式前一天，是国王的生日，大臣们为他准备了一个n×m(1≤n,m≤10000) 的蛋糕。他准备切蛋糕，但他切蛋糕有奇奇怪怪的癖好，他每次只切一刀，切下一个正方形蛋糕。请问它最多能切出多少个正方形蛋糕？

输入描述

第一行一个整数表示测试组数：T (0<T≤1000) 。

每组数据占一行，每行两个整数 n×m(1≤n,m≤10000)，表示蛋糕的大小。

输出描述

共 T 行，每行一个整数表示最多能切出的正方形蛋糕数量。

输入样例

2
2 3
2 5

输出样例

3
4

Hint

对于第一组数据，可切出一个 2×2, 两个1×1，共 3 个。

对于第一组数据，可切出两个 2×2, 两个1×1，共 4 个。

• 不需要考虑一开始输入的a就一定要大于b，因为如果a<b,a/b=0,r=a,经过一遍循环后会把a和b的值交换

#include <cstdio>

int main(){

    int t, a, b, ans, r;
    scanf("%d", &t);
    while(t--){
        ans = 0;
        scanf("%d%d", &a, &b);
        while(r = a % b){
            ans += a / b;
            a = b;
            b = r;
        }
        printf("%d\n", ans + a / b);
    }
    return 0;
}