Number Base Conversion Recovery

Little Blue has n numbers. Each number was converted into one of the bases \(2, 4, 8, 16\), where the hexadecimal representation uses uppercase letters A to F for digits greater than or equal to 10.

However, for each converted number \(A_i\) he forgot which base was used. He only remembers the converted string \(A_i\) and that its original decimal value should be at most \(B_i\). Your task is to determine the original decimal value for each number. If there is not exactly one possible value, output \(-1\).

inputFormat

The first line contains an integer n (\(1 \le n \le 10^5\)), representing the number of numbers.

Each of the following n lines contains a string A and an integer B separated by a space. The string A is the converted representation (which may include digits and uppercase letters A-F), and B is the upper bound for the original decimal value.

outputFormat

For each number, output the original decimal value on a separate line if it is uniquely determined. Otherwise, output \(-1\).

sample

3
100 100
1A 30
1F 10

-1
26
-1