URI Online Judge | 2736

Avalon Numbers

By Giovana Delfino, USP BR Brazil

Timelimit: 2

In a galaxy far far away there is a different and diversified kingdom called Avalon. A peculiar custom in Avalon is the way their residents deal with numbers. Depending of the month m and year y that they are currently in, the avalonians don't accept numbers that contain the sequence of digits m or the sequence of digits y among their numbers, for example, if m = 3 and y = 12 avalonians don't accept 3 or 12 or 123 or 736 or 5128 but they do accept 102.

Amanda and Krista are the queens of Avalon and their biggest concern is to keep the kingdom safe and free of invaders. Some time ago they found out that there is a prophecy that maps the name of the invaders to the amount of soldiers needed to defeat them. Since this prophecy is very important, the queens didn't measure efforts to find it and after a countless number of expeditions they finally did. Unfortunately there is a problem, the prophecy was written by a resident from Earth and therefore it doesn't follow the numerical system of Avalon.

The queens are desperate and hired you to make a program that given the current month and year y and the number n found in the prophecy your job is to convert n to the numerical scale of month m and year y, that is, calculate the n-th number of the numerical scale of month m and year y. For instance, if y = 12, m = 3 and n = 13 then the transformed number is 16, because the first 13 numbers of the avalonian scale are 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 14, 15, 16.

Input

Each test case contains a single line with 3 integers n (1 <= n <= 1018), m(1 <= m <= 9) and y (10 <= y <= 99), corresponding to the number found in the prophecy and the current month and year in Avalon, respectively.

Output

For each test case print a single number indicating n-th number of the numerical system in month m and year y.

Input Sample Output Sample

1 2 35
13 3 12
100 1 11
5 5 99
404 4 13

1
16
232
6
616