Problem Description

A $N$-ary number system is a counting system where a digit advances to the next place value after reaching $N$. For example, the decimal system, which is widely used in everyday life, is a base-10 system, while computers typically use a base-2 system. Additionally, base-8 and base-16 systems are also commonly used in certain contexts (in base-16, letters A through F are generally used to represent values 10 to 15; for this problem, base-11 to base-15 systems follow a similar convention).

In this problem, we will provide several numbers in different bases. You need to convert each of them into a decimal number.

Input Format

The first line of input is an integer $N$ represented in decimal. Following this, there are $N$ lines, each containing an integer $K$, followed by a space, and then a number in base $K$ that needs to be converted. It is guaranteed that all base $K$ numbers consist of digits and uppercase letters, and do not start with a zero. The base $K$ numbers are guaranteed to be valid.

It is guaranteed that $N \le 1000$; $2 \le K \le 16$.

It is also guaranteed that the number of digits in all base $K$ numbers does not exceed 9.

Output Format

Output $N$ lines, each containing a decimal number, representing the decimal value of the corresponding base $K$ number.

Sample Input and Output

Sample Input #1

2
8 1362
16 3F0

Sample Output #1

754
1008

Sample Input #2

2
2 11011
10 123456789

Sample Output #2

27
123456789

Notes

For any $L$-digit number in base $K$, assuming the rightmost digit is at position 0 and the leftmost digit is at position $L-1$, we can convert it to a decimal number by multiplying the digit at position $i$ by the weight $K^i$, and then summing the results for all positions. Here are two examples:

1. The octal number 1362 converts to a decimal number as follows: $1×8^3+3×8^2+6×8^1+2×8^0=754$;

2. The hexadecimal number 3F0 converts to a decimal number as follows: $3×16^2+15×16^1+0×16^0=1008$.

见题面 Input 部分

见题面 Output 部分