In a village named CodeVillage, there lived a farmer named Digo. Digo had a very greedy wife. Once Digo bought a 'bitstream' from the the market. Bitstreams are very tasty and can be eaten part by part for many days. But Digo's wife likes only those part of bitstream who can be expressed as a power of her desire 'd' by converting to decimal. Suppose a part is '1001' , it can be expressed as a power of 3 and 9.
Now since she wants to eat all the bitstream herself, and as quick as possible by eating one part daily, help her to do so.

Input:
First line contain t, number of testcases.
Next t line contains 'bitstream' and 'd' separated by a space.

Output:
't' lines, the minimum number of days required to consume the bitstream. If she cant consume by herself, print -1.

Constraints:
t is less than 20.
Bitstream contains upto 50 characters and each being either 1 or 0.
Desire is less than 100.

Explanation
1) Digo's wife dont eat bitstream parts that are not power of her desire. '0' cannot be broken into parts that she will eat.
2) She will eat whole bitstream in 1 day as '1' is a power of 5.
3) She will eat whole bitstream in 1 day as '111' is a power of 7.
4) '111111' can be divided into two parts '111'+'111' and can be eaten in two turns.
5) '110111110101' cant be broken into parts such that all parts are the power of 5.