Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

I am Good

By Zeronfinity · Limits 2s, 512 MB

I am trying to become a good guy, because it doesn’t take money to become good. So here’s a short and simple problem statement because I am a good guy! :)

Given two integers $X$ and $P$, find the minimum positive value of $K$ such that $f(X, K)$ is divisible by $P$.

$f(X, K)$ is defined as the $K$-times concatenation of the integer $X$ (without leading zeroes).

For example, $f(123, 3) = 123123123$,
$f(54, 4) = 54545454$,
$f(123, 2) = 123123$,
$f(7, 5) = 77777$

Input

Input will start an integer $T$ denoting the number of test cases.

In each test case, two space separated integers $X$ and $P$ will be given.

Constraints

$1 \leq T \leq 10$
$1 \leq X \leq 10^4$
$1 \leq P \leq 10^{10}$

Output

For each test case, print the minimum positive value of $K$ in a single separate line.
If no such $K$ exists, print -1.

Sample

InputOutput
2
123 9
123 10
3
-1

In the first test case, $f(123,3)=123123123$ is divisible by 9 while $123123$ and $123$ are not divisible by 9. Thus 3 is the minimum possible value of $K$ for this test case.

In the second test case, $f(123,K)$ can never be divisible by 10 no matter what $K$ is.


Discussion

Statistics


17% Solution Ratio

EgorKulikovEarliest, 3w ago

EgorKulikovFastest, 0.0s

EgorKulikovLightest, 131 kB

rebornShortest, 1076B

Submit

Login to submit

Related Contests

Criterion 2020 Round 1 Ended at 2020-01-31 11:30:00 +0000 UTC