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).
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.
For each test case, print the minimum positive value of K in a single separate line.
If no such K exists, print -1.
2 123 9 123 10
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.