Binary String

Time Limit: 3000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2847
64-bit integer IO format: %I64d      Java class name: Main

Description

Give you a binary string, you can add some 1s or 0s at any places of the string. Then the result divide by K, and the remainder should be zero. Please print string of the result, if there are more, print the one with the smallest length, if still more, print the smallest lexicographical one. If there is no such result print impossible.

Input

No more than 10 test cases. For each test case first line is a nonempty binary string whose length is no more than 20 and without leading zeros. Next line is an integer K(1 <= K <= 200).

Output

Print the result described above.

Sample Input

1000
4
11101
34
11010
70

Sample Output

1000
10101010
11010010

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .