给定正整数 $a,b$，称一个正整数二元组 $(x,y)$ 合法，当且仅当：

• $1 \le x,y,x^y\le a$。
• $x^y$ 是 $b$ 的倍数。

求满足以上条件的合法二元组数量。

输入格式

第一行一个正整数 $T$ 表示数据组数。

对于每组数据，输入一行两个正整数 $a,b$。

输出格式

对于每组数据输出一行一个非负整数表示答案。

样例

样例输入 #1

3
5 2
114514 5
1919810 1

样例输出 #1

3
22985
3841219

样例解释 #1

对于第一组数据：$(2,1),(2,2),(4,1)$ 合法。

数据范围与约定

对于所有数据，有：

• $1 \le T \le 5$
• $1 \le a,b \le 10^{12}$

测试点 $1(19pts)$：$a,b \le 100$。

测试点 $2(26pts)$：$a,b \le 2000$。

测试点 $3(8pts)$：$b \gt a$。

测试点 $4(17pts)$：$b \ge 2$。

测试点 $5(30pts)$：无特殊限制。