题目描述

Hanks 博士是 BT 领域的知名专家，他的儿子 Hankson 正在思考一个有趣的问题。

今天课堂上老师讲解了如何求两个正整数的最大公约数和最小公倍数。Hankson 开始思考这类问题的逆问题：已知正整数 $a_0, a_1, b_0, b_1$，设未知正整数 $x$ 满足：

1. $x$ 和 $a_0$ 的最大公约数是 $a_1$；
2. $x$ 和 $b_0$ 的最小公倍数是 $b_1$。

Hankson 想知道满足条件的正整数 $x$ 有多少个。

输入格式

第一行一个正整数 $n$，表示数据组数。
接下来 $n$ 行，每行四个正整数 $a_0, a_1, b_0, b_1$，用空格隔开。

输出格式

输出 $n$ 行，每行一个整数。若不存在满足条件的 $x$，输出 $0$；否则输出满足条件的 $x$ 的个数。

2
41 1 96 288
95 1 37 1776

6
2

提示

样例 1 说明

• 第一组数据中，$x$ 可以是 $9, 18, 36, 72, 144, 288$，共 $6$ 个。
• 第二组数据中，$x$ 可以是 $48, 1776$，共 $2$ 个。

数据规模与约定

对于全部的测试点，保证：

• $1 \leq n \leq 2000$
• $1 \leq a_0, a_1, b_0, b_1 \leq 2 \times 10^9$
• 保证 $a_0$ 能被 $a_1$ 整除，$b_1$ 能被 $b_0$ 整除

本题改编自 NOIP 2009 提高组 T2