Training Site
Sideways banner

Pablo's Homework

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 1.5 seconds

Pablo has done some homework for his maths class. Unfortunately, he believes some of his answers may be wrong. His homework consists of Q questions. For the i^\text{th} question, his answer was a_i. However, he knows that the answer must be divisible by x_i.

To remedy this, Pablo wants to remove some digits from the number he got to try and get the correct answer. To have the best possible chance of getting the right answer, he wants to remove as few digits as possible.

Please write a program to help Pablo with his homework. For each question, output a number divisible by x_i resulting from removing the smallest number of digits from a_i.

Note that you are not allowed to remove every digit (otherwise you would be left with nothing!). Additionally, your answer must not have any leading zeroes.

Input

  • The first line contains a single integer N.
  • Then, 2N lines follow, describing the questions. For the i^\text{th} question:
    • The first line contains a single integer, a_i.
    • The second line contains a single integer, x_i.

Output

For each question, if an answer exists, print it on a single line. Otherwise, print -1. There may be multiple possible answers, you may output any of them.

Constraints

Let d_i represent the number of digits in a_i.

  • 1 \le N \le 5{,}000
  • 0 \le a_i \lt 10^{5000} for all i
  • 2 \le x_i \le 1000 for all i
  • Additionally, the total number of digits across all a_i does not exceed 5,000.

Notes

  • a_i can be very large. It will not fit in most conventional number types in most programming languages. You may want to read it in as a string.
  • Python users should submit with Python 3.6 (PyPy 7.3) as this will generally make your solution run faster.
  • If you submit with Python or PyPy and get a Memory Limit Exceeded verdict, consider using array.array

Subtasks

  • Subtask 1 (+5%): N \le 10 and d_i \le 15 for all i.
  • Subtask 2 (+9%): x_i = 2 or x_i = 5
  • Subtask 3 (+16%): x_i is a factor of 100
  • Subtask 4 (+7%): x_i = 3
  • Subtask 5 (+12%): x_i = 9
  • Subtask 6 (+16%): x_i = 11
  • Subtask 7 (+16%): x_i is prime
  • Subtask 8 (+19%): No further constraints
  • Sample Input 1

    5
    27464
    3
    50555
    25
    10311
    9
    17462734263
    134
    18387428
    999
    

    Sample Output 1

    7464
    50
    0
    174627326
    -1