You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Now that the Four Divine Beasts have been freed and Calamity Ganon has been defeated, Hyrule once again enjoys peace. However, Link's challenges are far from over... Princess Zelda has been rescued by Link, and to ensure her happiness, he must learn to cook delicious meals for her. But Link is not skilled in cooking. He always struggles with the right balance of seasonings and the heat of the cooking. Now he needs your help, please write a program to help him cook the perfect dish!

Description

The taste of a dish can be represented by a k-digit decimal number n. To adjust the taste of the dish, you will do the following operation exactly once: choose exactly one single-digit number $x (0≤x≤9)$ and insert it into any position in n, making n become a new $(k+1)$-digit number m. For example: the 3-digit number 356 can have a digit 8 added at the end, making m=3568, a 4-digit number; or a digit 0 can be inserted between 3 and 5, making m=3056. Your goal is to make the taste of the dish perfect.The taste of a dish is considered perfect if and only if $c|m$(c is given).Note that '$|$' denotes the division symbol, $a|b$ means that b is divisible by a, in other words, $b = p·a (p ∈ Z)$, or $b$ $mod$ $a$ $= 0$.

Format

Input

Two lines: the first line contains an integer $t(1≤t≤10000)$ denotes the number of testcases;
The following $t$ lines contains two integers:$n(0≤n≤10^{12})$and $c(1≤c≤10)$, with a space seperated.

Output

Output $t$ lines, each line contains one integer,which is the specific $x$ that you chose.
If there are multiple answers, just print any of them.

Samples

4
638 6
0 2
100000 3
114514 5

1
2
2
5

Explaination

For the first example, one possible answer is 1 as we can insert '1' into the first position of '638' , makes it '1638', then 6 | 1638;
Similiar, the second:either 0->20 or 02 are all possible;
The third, for example:100000->1002000 is a possible answer.
It's guarantee that an valid answer always exists.