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

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 98765Output: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 |