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 XX and PP, find the minimum positive value of KK such that f(X,K)f(X, K) is divisible by PP.

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

For example,

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

Input

Input will start an integer TT (1T101 \le T \le 10) denoting the number of test cases.

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

Output

For each test case, print the minimum positive value of KK in a single separate line.

If no such KK exists, print -1.

Sample

InputOutput
2
123 9
123 10
3
-1

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

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


Discussion

Statistics


19% Solution Ratio

EgorKulikovEarliest, Jan '20

YouKnowWhoFastest, 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)=∑i=0K−110iLX=X∑i=0K−110iL=X10KL−110L−1f(X,...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.