Rani is teaching Raju maths via a game called N-Cube, which involves three sections involving N.

Rani gives Raju a number N, and Raju makes a list of Nth powers of integers in increasing order (1^N, 2^N, 3^N.. so on). This teaches him exponentiation. 
Then Raju performs the following subtraction game N times : Take all pairs of consecutive numbers in the list and take their difference. These differences then form the new list for the next iteration of the game. Eg, if N was 6, the list proceeds as [1, 64, 729, 4096 ... ] to [63, 685, 3367 ...], and so on 5 more times.
After the subtraction game, Raju has to correctly tell Rani the Nth element of the list. This number is the value of the game. 
After practice Raju became an expert in the game. To challenge him more, Rani will give two numbers M (where M is a prime) and R instead of just a single number N, and the game must start from M^(R - 1) instead of N. Since the value of the game can now become large, Raju just have to tell the largest integer K such that M^K divides this number. Since even K can be large, output K modulo 1000000007 (109+7).

-----Input-----

First line will contain T, number of testcases. Then the testcases follow
Each testcase contains of a single line of input, two integers M R

-----Output-----

For each testcase, output in a single line answer given by Raju to Rani modulo 1000000007.

-----Constraints-----

1<=T<=1000

2<=M<=109

30 points : 1<=R<=10000

70 points : 1<=R<=109

M is a prime number


-----Example-----
Input:

1

2 2

Output:

1

```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 = 'tc=int(input())\nfor case in range(tc):\n m,r=list(map(int,input().split()))\n n=m**(r-1)\n a=[i**n for i in range(1,2*n+1)]\n tmp=2*n-1\n for i in range(n):\n  for j in range(tmp-i):\n   a[j]=a[j+1]-a[j]\n print((a[n-1]/m)%1000000007)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13153