Edward 的任务是测量两台水泵的抽水速率。为此，他使用这两台水泵向一个水箱中抽水，并记录了在特定时间内抽入水箱的水量。

他发现，第一台水泵在 $b$ 秒内可以抽 $a$ 升水，第二台水泵在 $d$ 秒内可以抽 $c$ 升水。他还发现，当两台水泵同时工作时，它们在 $d$ 秒内一共可以抽 $b$ 升水。

不幸的是，Edward 不小心把水洒在了记录表上，导致他现在无法恢复 $a$ 和 $c$ 的值。不过，他记得这两个值都是正整数。现在他想知道，有多少种选择 $a$ 和 $c$ 的方式，能够与他的测量结果相吻合？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1000$) —— 测试用例的数量。

接下来的 $n$ 行，每行包含两个整数 $b$ 和 $d$ ($1 \le b, d \le 10^9$)。

输出格式

对于每个测试用例，输出一个整数 —— 选择 $a$ 和 $c$ 的方法数。每个答案占独立的一行。

样例

输入样例 1

3
9 6
40 60
60 40

输出样例 1

4
13
29

说明

在第一个测试用例中，可能的取值为：

• $a = 3, c = 7$；
• $a = 6, c = 5$；
• $a = 9, c = 3$；
• $a = 12, c = 1$。