# 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 ≤ T ≤ 10) denoting the number of test cases.

In each test case, two space separated integers X (1 ≤ X ≤ 104) and P (1 ≤ P ≤ 1010) 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.

• NumberTheory

### Statistics

19% Solution Ratio

EgorKulikovEarliest, 7M ago

EgorKulikovFastest, 0.0s

EgorKulikovLightest, 131 kB

rebornShortest, 1076B

### Submit 