C. Strong Password
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Zunaid is notoriously forgetful. To make his life easier, he always sets his computer password using a combination of his favorite digits: $$$0$$$ and $$$d$$$. He usually sticks to predictable, simple patterns—like a sequence of $$$d$$$s followed by some $$$0$$$s (e.g., $$$dddd0000$$$), or simple repeating arrangements that his forgetful mind can easily retrace (e.g., $$$dd00dd$$$ or $$$d0d0d0$$$).

His roommate, Imtiaz, considers himself a bit of a detective. He has spent months "studying" Zunaid's habits and has successfully cracked the password dozens of times. On a particularly chilly winter night, Zunaid decided he'd had enough. He set a new password, stood by the door, and smirked at Imtiaz.

"I'm heading over to CDS for a bit. I've set a password so strong that you can never deduce it. If you can crack it before I return, I'll treat you to an IUTian's Pizza tomorrow. If not, you owe me."

The inner detective in Imtiaz couldn't refuse. As soon as the door clicked shut, he pulled out a cheap UV flashlight. Shining it over the keypad, he saw deep, glowing marks only on the $$$0$$$ and $$$d$$$ keys, just as he had suspected. He noticed a hint on the lock screen: "Divisible by $$$n$$$." He also knew a password could consist of at most $$$n$$$ digits.

Luck wasn't on Imtiaz's side. Zunaid returned much earlier than expected. However, Imtiaz confidently claimed he had already deduced the password's logic and surely could have cracked it if he had been given five more minutes. Hearing his deductions, Zunaid laughed and replied, "Deducing the properties was the easy part! I'll still buy the pizza if you can actually give me any positive integer that follows the properties:"

  • Consists only of digits $$$0$$$ and $$$d$$$.
  • Is divisible by $$$n$$$.
  • Has a length of at most $$$n$$$ digits.
  • Does not contain any leading zero

Time is running out. Can you help Imtiaz get the free pizza?

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each test case consists of a single line containing two integers $$$n$$$ and $$$d$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le d \le 9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$. For each test case, it is guaranteed that at least one such positive integer exists.

Output

For each test case, output a positive integer in a line that consists only of the digits $$$0$$$ and $$$d$$$, is divisible by $$$n$$$, contains no leading zero and has a length that does not exceed $$$n$$$.

If there are multiple solutions, you may output any of them.

Example
Input
3
6 4
9 3
6 3
Output
4440
333333333
303330
Note

In the first test case, $$$n = 6$$$ and $$$d = 4$$$. The output $$$4440$$$ is a positive integer of length $$$4 \le 6$$$. It consists only of $$$4$$$ and $$$0$$$, and it is divisible by $$$6$$$.

In the second test case, $$$n = 9$$$ and $$$d = 3$$$. The output $$$333333333$$$ consists only of the digit $$$3$$$. Its length is $$$9 \le 9$$$, and it is divisible by $$$9$$$.

In the third test case, $$$n = 6$$$ and $$$d = 3$$$. The output $$$303330$$$ is a positive integer of length $$$6 \le 6$$$. It consists only of $$$3$$$ and $$$0$$$, and is divisible by $$$6$$$.