human
Can you provide a Python code to find the k-th special number if they are sorted in increasing order given the following:
Theofanis really likes sequences of positive integers, thus his teacher (Yeltsa Kcir) gave him a problem about a sequence that consists of only special numbers.

Let's call a positive number special if it can be written as a sum of different non-negative powers of n. For example, for n = 4 number 17 is special, because it can be written as 4^0 + 4^2 = 1 + 16 = 17, but 9 is not.

Theofanis asks you to help him find the k-th special number if they are sorted in increasing order. Since this number may be too large, output it modulo 10^9+7.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The first and only line of each test case contains two integers n and k (2 ≤ n ≤ 10^9.
1 ≤ k ≤ 10^9).

Output

For each test case, print one integer — the k-th special number in increasing order modulo 10^9+7.

Example

Input

3
3 4
2 12
105 564

Output

9
12
3595374

Note

For n = 3 the sequence is [1,3,4,9...]
from
assistant
#Here is Python code to find the k-th special number if they are sorted in increasing order.
collections import Counter, defaultdict, deque
import bisect, heapq
from sys import stdin, stdout
from itertools import repeat
import math

def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re

def inst():
    return raw_input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

mod = int(1e9+7)

def qmod(a, b):
    res = 1
    while b:
        if b&1:
            res = (res*a)%mod
        b >>= 1
        a = (a*a)%mod
    return res

def inv(a):
    return qmod(a, mod-2)

def my_main():
    kase = inp()
    pans = []
    for ka in range(kase):
        # print 'Case #%d: ' % (ka+1),
        n, k = inp()
        ans = [0]
        def kth(kk):
            if not kk:
                return
            if kk==1:
                ans[0] += 1
                return
            per = 1
            now = 1
            for i in range(2, 40):
                if per*2 > kk:
                    ans[0] += now
                    kth(kk - per)
                    break
                per *= 2
                now *= n
                now %= mod
        kth(k)
        pans.append(str(ans[0]%mod))
    print '\n'.join(pans)

my_main()