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

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

3
7 3
15 4
31 5

1
1
1

Hint

【样例解释 #0】

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