CSG-CPC
Online Judge

1245 : 不定方程

         Time Limit: 1 Sec     Memory Limit: 512 Mb     Submitted: 910     Solved: 138    

Description

给定正整数 \(n,k\),求不定方程 \(a^k-b^k=n\) 的正整数解数量。

Input

输入第一行一个整数 \(T\)\(1 \le T \le 20\)) 表示询问数量。之后 \(T\) 行,每一行两个整数 \(n,k\) 表示一次询问。保证 \(1 \le n \le 10^{18}\)\(3 \le k \le 64\)

Output

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

Sample

3
7 3
15 4
31 5
1
1
1

Hint

【样例解释 #0】

三个不定方程的唯一解都是 \((2,1)\)

Author

THU