Pablo's Homework

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