CONCATE - Integer Concatenation

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 separate 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:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Based on a topcoder problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.