Base Conversion

Problem Description

A base-$N$ numeral system counts by carrying one whenever $N$ is reached. For example, people mostly use decimal in daily life, while computers generally use binary at the bottom level. Besides, octal and hexadecimal are also commonly used in some contexts (in hexadecimal, letters A to F usually represent ten to fifteen; similarly in this problem for bases eleven to fifteen).

In this problem we give $N$ 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$ in decimal. The following $N$ lines each contain an integer $K$, then a space, followed by a base-$K$ number to be converted. It is guaranteed that all base-$K$ numbers consist only of digits and uppercase letters, and do not start with $0$. The base-$K$ numbers are guaranteed valid.

Output Format

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

Sample Input 1

2
8 1362
16 3F0

Sample Input 2

2
2 11011
10 123456789

Sample Output 1

754
1008

Sample Output 2

27
123456789

Sample Explanation

In the first sample, there are two lines. The first line's base-$8$ number 1362 converts to decimal: $1 \times 8^3 + 3 \times 8^2 + 6 \times 8^1 + 2 \times 8^0 = 754$. The second line's base-$16$ number 3F0 converts to decimal: $3 \times 16^2 + 15 \times 16^1 + 0 \times 16^0 = 1008$ (where F stands for $15$). So the outputs are $754$ and $1008$ respectively.

Constraints

• $N \le 1000$;
• $2 \le K \le 16$;
• all base-$K$ numbers have at most $9$ digits.