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 baseN(N, B, numerals, carry=False):
    I = ''
    while N > 0:
        R = N % B
        I = numerals[R] + I
        N /= B
        if R == 0 and carry: N -= 1
    return int(I or '0')

def m(k):
    v = '0123456789'
    return v[:k] + v[k+1:]

def process(N, L):
    if L == 0:
        return baseN(N, 9, '912345678', True)
    else:
        return baseN(N, 9, m(L))

def main():
    T = int(raw_input())
    for t in xrange(T):
        N, L = map(int, raw_input().split())
        print process(N, L)

main()