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.

见题面

见题面