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