Migrated from Lutece 754 一个忧伤的问题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你两个数$G$和$L$，请你求出有多少个有序三元组$(x,y,z)$可以满足$\gcd(x,y,z)=G$并且${\rm lcm}(x,y,z)=L$?

其中，$\gcd$表示$x,y,z$的最大公约数，$\rm lcm$表示$x,y,z$的最小公倍数。

注意：$(1,2,3)$和$(1,3,2)$是两个不同的答案。

Input

包含多组数据。

第一行只含一个$T$（$T\leq 12$)，表示$case$个数。

接下来$T$行，每行只含两个数$G$和$L$，$1\leq G,L\leq 10^9$

Output

对每一个$case$，输出一个整数，表示有序三元组的个数。

Samples

2
6 72
7 33

72
0

Resources

2013 UESTC ACM Training for Math