题目描述

给定正整数 $G$ 和 $L$，请统计有多少对有序正整数对 $(x,y)$ 同时满足：

有序的含义是：当 $x\ne y$ 时，$(x,y)$ 与 $(y,x)$ 算两对。

共有 $T$ 组询问，对每组询问输出答案。

输入格式

第一行一个整数 $T$，表示询问组数。

接下来 $T$ 行，每行两个正整数 $G,L$，用空格分隔。

输出格式

$T$ 行，每行一个整数，表示满足条件的有序数对数量。若不存在这样的数对，输出 0。

样例输入1

2
6 72
5 8

样例输出1

4
0

样例输入2

2
2 60060
1 1

样例输出2

64
1

数据范围与约定

• $1\le T\le 100$
• $1\le G,L\le 2\times 10^9$
• 保证答案不超过 $10^9$

提示

如果 $L$ 不是 $G$ 的倍数，显然无解。

否则令 $K=\dfrac{L}{G}$，并设 $x=G\cdot a,\ y=G\cdot b$。代入两个条件可以得到：

也就是说，要把 $K$ 的每个质因子（连同它的完整幂次）整个分给 $a$ 或整个分给 $b$：因为 $\gcd(a,b)=1$，同一个质数不能两边都有。

设 $K$ 的不同质因子个数为 $\omega(K)$（只数有几种质数，不数幂次），每个质因子有“分给 $a$”和“分给 $b$”两种选择，于是：

用试除法分解 $K$，每发现一个新的质因子就让答案乘以 $2$ 即可。特别地，$K=1$ 时 $\omega(K)=0$，答案为 $1$（数对 $(G,G)$）。