# 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$ ($1 \le T \le 10$) denoting the number of test cases.

In each test case, two space separated integers $X$ ($1 \le X \le 10^4$) and $P$ ($1 \le P \le 10^{10}$) will be given.

## 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.

### Statistics

19% Solution Ratio

EgorKulikovEarliest, Jan '20

YouKnowWhoFastest, 0.0s

EgorKulikovLightest, 131 kB

rebornShortest, 1076B

### Editorial

Let L be the length of X (number of digits). Then, f(X,K)=∑i=0K−110iLX=X∑i=0K−110iL=X10KL−110L−1f(X,...

### Related Contests

 Criterion 2020 Round 1Ended Jan '20