LEXIPOS - Lexicographic position

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 QN,K. For example, Q11,2 = 4.

Given N and K, compute QN,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 QN,K on a single line.

Constraint

1 ≤ T ≤ 100

1 ≤ K ≤ N ≤ 10100

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

Added by:Race with time
Date:2010-10-15
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:Based on a problem from ACM NEERC 2002 - 2003

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.