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...]
import bisect
import math
from collections import deque
import heapq

mod =  1000000007 
N = 200005

def mul(a, b):
	return (a*b)%mod

def add(a, b):
	return (a+b) if (a+b<mod) else (a+b)-mod

def sub(a, b):
	return (a-b) if (a-b>0) else (a-b)+mod

def powr(a, b):
	ans = 1
	while b>0:
		if b & 1:
			ans=mul(ans,a)
		a = mul(a,a) 
		b//=2
	return ans

def inv(n):
	return powr(n, mod-2)

def factlist():
	fact = [1]
	for i in range(1, N):
		fact.append(mul(fact[i-1],i))
	return fact

def invfactlist(fact):
	invfact=[0]*N
	invfact[0]=1
	invfact[N-1]= inv(fact[N-1])
	for i in range(N-2, 0, -1):
		invfact[i]= mul(invfact[i+1],(i+1))
	
	return invfact

def rot(S):
	return list(zip(*S[::-1]))

def gcd(a, b):
	if b==0:
		return a
	return gcd(b, a%b)

def generate():
	ans = [0]
	while ans[-1]<1000000000:
		ans.append(1+ans[-1]*2)
	return ans

def main():
	dp = generate()
	# print(dp[:10])
	t = int(input())
	while t:
		t-=1
		n,k  = map(int, input().split())
		ans = 0
		while k>0:
			ind = bisect.bisect_right(dp, k-1)
			p = powr(n, ind-1)
			ans = add(ans, p) 
			k-= (dp[ind-1]+1)
			# print(ans, p)
		print(ans)
	



if __name__ == "__main__":
    main()
    
	