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 ^ length(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