If an integer is not divisible by 2 or 5, there will be some multiple of that number in decimal notation with a sequence of only a digit.

For example, you have to find a multiple of 3 which contains only 1's. Then the result 111 (3-digit) divisible by 3. Similarly, if you are finding some multiple of 7 which contains only 3's then, the result is 333333 which is divisible by 7.

Now, you are given the number and the only allowable digit, you should report the number of digits of such a multiple.

Input

Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case will contain two integers n (0 < n ≤ 10⁶ and n will not be divisible by 2 or 5) and the allowable digit (1 ≤ digit ≤ 9).

Output

For each case, print the case number and the number of digits of such multiple. If several solutions are there; report the minimum one.

Sample

Sample Input	Sample Output
Click to copy 3 3 1 7 3 9901 1	Click to copy Case 1: 3 Case 2: 6 Case 3: 12

Notes

For case 1, 111 is the smallest integer, and it contains 3 digits.
For case 2, 333333 is the smallest integer, and it contains 6 digits.

Total Submissions

Users Tried

Users Solved

LOJ 1078 - Integer Divisibility

Hint

If your data type is even long long int (in C++ it is the highest data type), it can not hold the sequence and because of overflow as there may be 10^6 digit.
If your data type is string then you will get “time limit exceeded” .

So simply check divisibility digit by digit such as if input is 3 1 then number is = 111 . So at first check 1 then 11 and last 111. That remainder r can be checked by this rule (if n is 3 and m is 1) r=(r*10+m)%n
Continue this until reminder becomes 0. Also note down how may times this operation need.

Prerequisites : Modular Arithmetic

Code

C++


#include <bits/stdc++.h>
using namespace std;

void _main_main()
{
    int percent , digit , rem = 0 ;
    cin >> percent >> digit ;

    int cnt = 0 ;
    while (1)
    {
        rem = (rem *10 + digit)%percent ;
        cnt++ ;
        if (rem == 0) break ;
    }
    cout << cnt << "\n" ;
}

int main ()
{
    int testCase = 1 ; cin >> testCase ;
    for (int i = 0; i < testCase; i++){
        cout << "Case " << i+1 << ": " ;
        _main_main() ;
    }
}

Happy Coding!

Written by: Moontasir Mahmood

Tutorial source