The evil problem setter has to set a problem. But he cannot find a good problem to set. After thinking long and hard he came up with a problem.
He gives you a string s consisting of decimal digits. He also gives you a integer x. Then he asks you to find the length of the shortest substring of s which is divisible by x. Simple, right?
Well as we said before, the problem setter is evil. So, he wants to make your life difficult. He says that not all decimal strings represent a valid number. A decimal string is valid if and only if it is "0", or it does not start with a 0. For example - "0", "1", "12", "100" are valid strings, but "00", "012", "0056" are not. He asks you to find the length of the shortest valid substring of s which is divisible by x.
Although the problem setter is evil, he still has a little good left in his heart. So, he will make sure that x is not divisible by 2 or 5.
Input
The first line contains a single integer the number of testcases t. (1 ≤ t ≤ 10)
The first line of each case contains decimal string s. (1 ≤ length(s) ≤ 105).
The second line of each case contains a single integer x, (1 ≤ x≤ 109). It is guaranteed that x is not divisible by 2 or 5.
Output
For each case, output a single integer - the length of the shortest valid substring of s which is divisible by x.
If there are no such string, print -1.
Sample
| Input | Output |
|---|---|
5 21574 3 23257 7 5123 37 5214056 17 152153143 179 | 2 1 -1 1 5 |
