The chef was playing with numbers and he found that natural number N can be obtained by sum various unique natural numbers, For challenging himself chef wrote one problem statement, which he decided to solve in future.
Problem statement: N can be obtained as the sum of Kth power of integers in multiple ways, find total number ways?
After that Cheffina came and read what chef wrote in the problem statement, for having some fun Cheffina made some changes in the problem statement as.
New problem statement: N can be obtained as the sum of Kth power of unique +ve integers in multiple ways, find total number ways?
But, the chef is now confused, how to solve a new problem statement, help the chef to solve this new problem statement.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, two integers $N, K$. 

-----Output:-----
For each test case, output in a single line answer to the problem statement.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 1000$
- $1 \leq K \leq 6$

-----Sample Input:-----
2
4 1
38 2

-----Sample Output:-----
2
1

-----EXPLANATION:-----
For 1) 4 can be obtained by as [ 4^1 ], [1^1, 3^1], [2^1, 2^1]. (here ^ stands for power)
But here [2^1, 2^1] is not the valid way because it is not made up of unique +ve integers. 
For 2) 38 can be obtained in the way which is [2^2, 3^2, 5^2] = 4 + 9 + 25

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'for _ in range(int(input())):\n    x,n = map(int,input().split())\n    reach = [0]*(x+1)\n    reach[0] = 1\n    i=1\n    while i**n<=x:\n        j = 1\n        while j+i**n<=x:\n            j+=1\n        j-=1\n        while j>=0:\n            if reach[j]>0:\n                reach[j+i**n]+=reach[j]\n            j-=1\n        i+=1\n    #print(reach)\n    print(reach[-1])'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13165