1245 : 不定方程

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
512 兆MB
提交次数Submitted
1,468 次Times
通过次数Solved
216 次Times

题目描述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

提示Hint

【样例解释 #0】

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

出题Author

THU