3373 -- Changing Digits

Language:

Changing Digits

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 4160		Accepted: 1384

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:

m contains no leading zeros and has the same length as n (We consider zero itself a one-digit integer without leading zeros.)
m is divisible by k
among all numbers satisfying properties 1 and 2, m would be the one with least number of digits different from n
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≤10¹⁰⁰) and k(1≤k≤10⁴, k≤n) 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

Sample Output

2
119103

Source

POJ Monthly--2007.09.09, Rainer