Let us consider the set of integer numbers between 1 and N inclusive. Order them lexicographically (i. e. like in the vocabulary), for example, for N = 11 the order would be: 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.

Denote the position of the number K in this ordering as Q_N,K. For example, Q_11,2 = 4.

Given N and K, compute Q_N,K.

Input

The first line contains a number T, which is the number of test cases. T lines follow, each contains 2 integers N and K separated by a single space.

Output

For each test case, print Q_N,K on a single line.

Constraint

1 ≤ T ≤ 100

1 ≤ K ≤ N ≤ 10¹⁰⁰

Example

Input: 
7
1 1
11 2
215 211
215 215
215 26
215 99
1000000000 999999999

Output: 
1
4
126
130
135
215
1000000000