TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7828
  • 题目
  • P7828切蛋糕
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    有一个国家,这里有一个国王,这一天国王过生日,下面的大臣给国王买了一个 \(n \times m\) 的蛋糕,现在这些大臣准备分蛋糕,由于国王非常喜欢正方形,大臣们为了让国王开心,每一次切蛋糕的时候都会切当前尺寸蛋糕能满足的最大的正方形部分,例如 $4 \times 6$的蛋糕,第一次肯定切 $1$ 个 $4 \times 4$ 的,然后剩下 $2 \times 4$ ,第二次切 $2 \times 2$ 的,依次类推。现在大臣们想知道在所有蛋糕均为正方形的时候,能切多少个蛋糕

    输入格式

    输入第一行一个整数 \(T\) ,代表有 \(T\) 组测试数据

    接下来 \(T\) 行,每一行输入 $2$ 个数 \(n\)\(m\)

    $1\le T \le10^4$

    $1\le n,m\le10^6$

    输出格式

    对于每一组测试数据,输出对应答案

    样例输入

    2
    2 3
    2 5

    样例输出

    3
    4