SUFFIX - Suffixes

Find the smallest natural number X such that, if we write X in bases B1, B2 ... BN, we get strings with suffixes S1, S2 ... SN, 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 kth of the next N lines there is an integer Bk (2 ≤ Bk ≤ 36) and a suffix Sk from the task description.

The given bases will be pairwise distinct. Also, the product of the powers Bk ^ length(Sk) will be less than 1018.

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

Added by:Adrian Satja Kurdija
Date:2015-04-05
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own problem.

hide comments
2015-05-23 12:23:35 Adrian Satja Kurdija
@Szymon: try this one

3
9 71
29 H
16 2F14
2015-05-20 17:02:47 Szymon
@Adrian
can you give me more tests?
have no idea why SIGFPE occures, my code answers properly for both imputs from example and this provided by you in comments...
2015-04-30 12:09:25 Adrian Satja Kurdija
@tarunsingal: Yes, it is the right direction. In order to find the intersection of arithmetic progressions, use [spoiler removed].

Last edit: 2015-12-21 07:34:01
2015-04-21 06:30:56
Hi Adrian,
I am trying to formulate this problem as follows:
Each (b,s) pair can be represented as an arithmetic series. If we can find an arithmetic series, if it exists, which contains terms common to all n arithmetic series( as there are n (b,s) pairs) then first term of this series will be required output.
Do you think I am thinking in right direction? Or can you suggest some direction?
Tarun.
2015-04-16 13:09:15 Adrian Satja Kurdija
@tarunsingal: 560093690230
2015-04-16 05:47:09
Thanks Adrian for test vector.
Can you also provide its output value?
2015-04-15 15:23:51 Adrian Satja Kurdija
@tarunsingal: try this one

5
9 737
20 BA
19 25
31 5G
23 5
2015-04-15 11:33:46
My solution is exceeding time limit. Can you provide some test case which may help me reproduce this issue on my local machine?
2015-04-07 19:23:17 Adrian Satja Kurdija
@Pradd: Everything is fine. 22 is a suffix of 422 and 4 is a suffix of 64.
2015-04-07 12:08:28 Pradd
There appears to be some mistakes in the first test case. 112 in Base 5 gives 422 not 22 and 112 in base 18 gives 64 not 4.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.