Problem of The Week (18/09/2009)

QuickSums

Problem Statement

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual.

For example, consider the string "12" (quotes for clarity). With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get "1+2", which evaluates to 3. So, in that case, given "12", a minimum of 1 addition is required to get the number 3. As another example, consider "303" and a target sum of 6. The best strategy is not "3+0+3", but "3+03".

You can do this because leading zeros do not change the result.

If this is impossible, return -1.

Input

First line contains a single integer T. T number of cases follow. Each case consists of a string of digits S and the target integer R.

Output

Output must contain T lines, corresponding to each test case, each line K must contain an integer P corresponding to the minimum number of additions required in the string S, of the Kth input, to equal integer R, of the Kth input.

Constraints
1 <= Number of characters in S <= 10
0 <= R <= 100

Sample

Input

6
99999 45
1110 3
0123456789 45
99999 100
382834 100
9230560001 71

Output

4
3
8
-1
2
4

Notes:

Case 1) In this case, the only way to achieve 45 is to add 9+9+9+9+9. This requires 4 additions.
Case 2) Be careful with zeros. 1+1+1+0=3 and requires 3 additions.
Case 4) When sum not possible, output should be -1
Case 5) There are 3 ways to get 100. They are 38+28+34, 3+8+2+83+4 and 3+82+8+3+4. The minimum required is 2.