题目描述

给定一个具有整数边长的矩形，你的任务是将其切割成尽可能少的整数边长的正方形。

输入格式

第一行包含一个整数 $T$ —— 测试用例的数量 $(1 \le T \le 3600)$。接下来的 $T$ 行中的每一行包含两个整数 $w_{i}, h_{i}$ —— 矩形的尺寸 $(1 \le w_{i}, h_{i} \le 60$；对于任何 $i \neq j$，要么 $w_{i} \neq w_{j}$，要么 $h_{i} \neq h_{j})$。

输出格式

对于第 $i$ 个测试用例，输出 $k_{i}$ —— 最小的正方形数量，使得可以将 $w_{i}$ 乘以 $h_{i}$ 的矩形切割成 $k_{i}$ 个正方形。

输入输出样例 #1

输入 #1

3
5 3
5 6
4 4

输出 #1

4
5
1