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.


Discussion

Statistics


19% Solution Ratio

EgorKulikovEarliest, 7M ago

EgorKulikovFastest, 0.0s

EgorKulikovLightest, 131 kB

rebornShortest, 1076B

Submit

Login to submit

Editorial

Let L be the length of X (number of digits). Then, $f(X,K) = \displaystyle\sum_{i=0}^{K-1}{10^{iL}}...

Related Contests