## 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