Description

Hanks 博士是 BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。

今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考「求公约数」和「求公倍数」这类问题的一个逆问题，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x满足：

1.x和a0的最大公约数是a1； 2.x和b0的最小公倍数是b1 。 Hankson 的「逆问题」就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。

Input Format

第一行为一个正整数n，表示有n组输入数据。 接下来的n行每行一组输入数据，为四个正整数a0,a1,b0,b1，每两个整数之间用一个空格隔开。 输入数据保证a0能被a1整除，b1能被b0整除。

Output Format

共n行。每组输入数据的输出结果占一行，为一个整数。 对于每组数据：若不存在这样的x，请输出0；若存在这样的x，请输出满足条件的x的个数。

Sample

输入

2
41 1 96 288
95 1 37 1776

输出

6
2

第一组输入数据，x可以是9,18,36,72,144,288，共有6个； 第二组输入数据， 可以是48,1776，共有2个。

Hint

对于50%的数据，保证有a0,a1,b0,b1<=10^4且n<=100 。 对于 的数据，保证有1=<a0,a1,b0,b1<=2*10^9 且n<=2000 。