human
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...]
assistant
#Here is Python program to find the k-th special number if they are sorted in increasing order.

from 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()