Imagine you are still a lowly high-school student (apologies to the lowly high-school students competing). You are bored in maths class (purely hypothetically). To amuse yourself, you are playing a game. The games works as follows. You want to find the largest non-negative multiple of a positive integer \(X\) such that the number of digits (in base 10) is exactly \(D\). Several of your friends have started playing. So you can shame them and their families, you have decided to write a program to play the game.
The first line of input contains an integer, \(T\) (\(1 \leq T \leq 100\)), the number of test cases. The next \(T\) lines each define a test case. A test case is defined by a line containing two space separated integers \(X\) and \(D\).
Display a single line for each test case. The largest possible multiple. If there is no valid multiple, display
Note this problem includes sub-problems of increasing difficulty worth different numbers of points:
- 20 points: \(1 \leq X \leq 1000\) and \(1 \leq D \leq 4\)
- 100 points: \(1 \leq X \leq 10^9\) and \(1 \leq D \leq 10\)
5 1 1 7 3 11 2 93 4 99 1
9 994 99 9951 0