Find the smallest natural number X such that, if we write X in bases B₁, B₂, ..., B_N, we get strings with suffixes S₁, S₂, ..., S_N, respectively.

The possible digits are 0123456789ABCDEFG...XYZ, with values 0..35. Of course, the number written in base B consists only of the digits with values between 0 and B - 1.

Input

In the first line of input there is an integer N (1 ≤ N ≤ 10) from the task description.

In k^th of the next N lines there is an integer B_k (2 ≤ B_k ≤ 36) and a suffix S_k from the task description.

The given bases will be pairwise distinct. Also, the product of the powers B_k ^ lenght(S_k) will be less than 10¹⁸.

Output

Print the required X, written in base 10.

Example

input
3
5 22
11 A2
18 4
output
112

input
5
2 110
32 E
25 M3
28 2
7 2

output
53678