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

import sys
sys.setrecursionlimit(100000)

def _r(): return sys.stdin.buffer.readline()
def rs(): return _r().decode('ascii').strip()
def rn(): return int(_r())
def rnt(): return map(int, _r().split())
def rnl(): return list(rnt())

def solve(n, k):
    mod = 10**9+7
    p = 1
    sol = 0
    while k:
        if k&1:
            sol = (sol + p) % mod
        p = (p * n) % mod
        k >>= 1
    return sol

for _ in range(rn()):
    n, k = rnt()
    print(solve(n, k))

# import collections

# def solve(n, edges):
#     g, q = [[] for _ in range(n)], collections.deque()
#     for f, t in edges:
#         f, t = f-1, t-1
#         g[f].append(t)
#         g[t].append(f)
#         if f == 0:
#             q.append((t, f))
#         if t == 0:
#             q.append((f, t))
#     sum_buds_leaves = num_buds = num_root_leaves = 0
#     while q:
#         node, parent = q.popleft()
#         bud_leaves = 0
#         for child in g[node]:
#             if child != parent:
#                 if len(g[child]) == 1:
#                     bud_leaves += 1
#                 else:
#                     q.append((child, node))
#         if bud_leaves > 0:
#             num_buds += 1
#             sum_buds_leaves += bud_leaves
#         else:
#             num_root_leaves += 1
#     sol = sum_buds_leaves - num_buds + 1
#     if num_root_leaves:
#         sol += num_root_leaves - 1
#     return sol
 
# for _ in range(rn()):
#     n = rn()
#     edges = [rnt() for _ in range(n-1)]
#     print(solve(n, edges))

# def solve(n, m, mat):
#     def _try(r, c, dr, dc):
#         sol = 0
#         for i in range(c+1, c+dc):
#             sol += 1 - int(mat[r][i])
#             sol += 1 - int(mat[r+dr][i])
#         for i in range(r+1, r+dr):
#             sol += 1 - int(mat[i][c])
#             sol += 1 - int(mat[i][c+dc])
#         for i in range(r+1, r+dr):
#             for j in range(c+1, c+dc):
#                 sol += int(mat[i][j])
#         return sol
#     sol = float('inf')
#     sols = [[0]*m for _ in range(n)]
#     for r in...