Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Changing Digits
 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 4144 Accepted: 1379

Description

Given two positive integers n and k, you are asked to generate a new integer, say m, by changing some (maybe none) digits of n, such that the following properties holds:

1. m contains no leading zeros and has the same length as n (We consider zero itself a one-digit integer without leading zeros.)
2. m is divisible by k
3. among all numbers satisfying properties 1 and 2, m would be the one with least number of digits different from n
4. among all numbers satisfying properties 1, 2 and 3, m would be the smallest one

Input

There are multiple test cases for the input. Each test case consists of two lines, which contains n(1≤n≤10100) and k(1≤k≤104, kn) for each line. Both n and k will not contain leading zeros.

Output

Output one line for each test case containing the desired number m.

Sample Input

```2
2
619103
3219```

Sample Output

```2
119103```

Source

[Submit]   [Go Back]   [Status]   [Discuss]