CONCATE - Integer Concatenation

no tags 

 

You are given two positive integers N and M. Your task is to find the least positive integer X such that
if N is concatenated X times it becomes divisible by M. if no such positive integer exists print -1 instead.
For example if 12 is concatenated 2 times it becomes 1212.
Given  1<=N<=1000000000 and 1<=M<=100000

You are given two positive integers N and M. Your task is to find the least positive integer X such that

if N is concatenated X times it becomes divisible by M. if no such positive integer exists print -1 instead.

For example if 12 is concatenated 2 times it becomes 1212.

Given  1<=N<=1000000000 and 1<=M<=100000

Input

 

First line contains the number of test cases 1<=T<=20. Each of the following T lines contains 2 integers N and M.

 

 

Output

 

For each test case print in a seperate line the required value of X or -1 if no such X exists.

 

Example

Input:
4
2 9
121 11
1 2
35 98765

Output:
9
1
-1
9876


Added by:Mahesh Chandra Sharma
Date:2011-01-09
Time limit:0.654s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Based on a topcoder problem