该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

吱吱吱——
众所周知，刘学习和许多人都在宿舍养了仓鼠。但是现在，仓鼠们遇到了鼠生的重大危机！海韵七的猫咪们盯上了仓鼠们，并密谋到宿舍偷仓鼠！

Description

已知：
有无限多只仓鼠，仓鼠们从1开始连续编号；
有x只猫咪，猫咪们有一个喜欢的数字k；
当满足某个条件时，编号为y的仓鼠会被猫咪们偷走。
刘学习为了保护自己的仓鼠，费尽心机地打听到了这个条件：若y为n位整数，从右往左第i位为\(a_i\)，则\(f(y,k) = \sum_{i=1}^{n}{a_i^k}\)。如：\(f(233,2) = {2^2} + {3^2} + {3^2} = 22\)。 当\(f(y, k) - y = x\)时，编号为y的仓鼠会被猫咪们偷走！现在着急的刘学习请你帮忙计算哪几只仓鼠可能会被偷走，但是时间紧急，你只来得及告诉他有几只仓鼠处于危险之中。

Format

Input

多组数据。
第一行一个整数T，代表数据组数。
对每组数据，第一行为x和k，意义如题所述。

Output

每组数据一行，每行一个数，为满足\(f(y, k) - y = x\)的y的数量。

Sample 1

Input

2
2 2 
3 2

Output

1
2

Limitation

1s, 1024KiB for each test case.

Hint

对100%的数据：
\(1<=T<=100\)
\(0<=x<={10^9}\)
\(1<=k<=9\)
对50%的数据：
保证可能被偷走的仓鼠编号y的位数不超过5位。

样例第一组数据解释：f(2, 2) - 2 = 2，编号y=2的仓鼠会被偷走。

Source

Vijos Original