Submit Best Submissions All Submissions

32. Identify the Number


Problem Statement:
You are given three numbers N, Q and R. You want to find M, such that:

 1. M is positive.
 2. The string decimal representation of M is a subsequence of the string decimal representation of     N, i.e. M can be obtained from the removal of zero or more digits from 3. the decimal     representation of N.
 4. M gives a remainder of R when divided by Q.
 5. M is the maximum possible.


Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 200). Next T lines contain the test cases, each on a single line.

Each case contains three integers, separated by single spaces, N, R, Q as described in the problem, in this order (1 ≤ N < 101,000,0 ≤ R < Q ≤ 1,000). All numbers in the input will not contain leading zeros.


Output Format:
For each test case, output, on a single line, the number M as described in the problem, with no leading zeros. If no such M can be found, output on a single line "Not found" instead.

In the first case below, 840 is divisible by 8, thus it is the largest possible value of M.

In the second case, the subsequences of 901 are {9, 0, 1, 90, 01, 91, 901}. Out of these there is 0 which is not positive and 01 which has a leading zero. Only 91 has a remainder of 3 when divided by 8.

In the third case, there is no subsequence of 123456789 that gives a remainder of 10 when divided by 100.


Sample Input:
3 840 0 8 901 3 8 123456789 10 100


Sample Output:
840 91 Not found





Added by: abdelkarim
Added at: 2014-02-26 01:15:00 UTC
Time Limit: 3 seconds
Partial score: No
Source:ACM Arab Collegiate Programming Contest 2011