Majin wants to label his N (1 ≤ N ≤ 1,000,000) towers. He has lost the labels with the digit L (0 ≤ L ≤ 9) written on them. Assume he has sufficient labels to complete the task.

If the towers are labeled with the smallest set of N positive integers that don't have the digit L, what is the largest number that Majin will label the tower as ?

Input

The first line has an integer 't' (1 ≤ t ≤ 10), the number of test cases. t cases follow.

Each test case containse two space-separated integers on a single line: N and L

Output

A single integer that is the largest number a tower can have.

Example

Input:
1
10 0

Output:
11

Explanation

The smallest 10 numbers he can use are: 1, 2, 3, 4, 5, 6, 7, 8, 9, and 11.
def calc2(n):
        tp=n
        s=''
        while tp>0:
                k=tp%9
                if(k==0):
                        k=9
                s=str(k)+s
                tp=(tp-k)/9
        return int(s)    
def calc1(n,d):
        di=dict()
        for i in range(0,9):
                if i<d:
                        di[i]=i
                else:
                        di[i]=i+1

        s=''
        tp=n
        while tp>0:
                s=str(di[tp%9])+s
                tp/=9
        return int(s)
inp=int(raw_input())
for t in range(0,inp):
        st=raw_input()
        ls=st.split()
        n=int(ls[0])
        d=int(ls[1])
        if d!=0:
                print calc1(n,d)
        else:
                print calc2(n)