Given a string of numbers with length ~N~ and a target ~T~, try to insert the minimum number of +s and *s so that the result is ~T~. The expression will follow the usual priority order: * take precedence over +. Operands may have arbitrary number of leading zeros. For example, 09 is a valid operand.

Input Specification

The first line of the inputs consists of an integer ~C~ ~(1 \leq C \leq 5)~ denoting the number of test cases.

For each test case, the first line is a string of length ~N~ ~(1 \leq N \leq 20)~ consisting of numbers ~0 \sim 9~. The second line is an integer ~T~ ~(0 \leq T \leq 250)~ denoting the target.

Output Specification

For each test case, output a line with an integer denoting the minimum number of + or * that should be inserted to make the expression equal to the target ~T~. If there are no solutions, output -1.

Sample Input

3
032089
5
333
9
000000000000000
0

Sample Output

3
2
0

Explanation

In the first test case, the optimal one is ~03 + 2 + 0 \times 89~. Recall that arbitrary number of leading zeros are allowed.

In the second test case, the optimal one is ~3 + 3 + 3 = 9~.

In the third test case, you don't have to insert any, so the answer is 0.

Constraints

For all test cases, ~1 \leq C \leq 5~, ~1 \leq N \leq 20~, ~0 \leq T \leq 250~.

Scoring

There are 20 test cases in total.

• For ~20\%~ of test cases, ~1 \leq N \leq 10, 0 \leq T \leq 50~.
• For ~40\%~ of test cases, ~1 \leq N \leq 15, 0 \leq T \leq 200~. (Note: this includes the first ~20\%~ of test cases).
• For another ~10\%~ of test cases, the output is either 1 or -1.
• For another ~20\%~ of test cases, you only need to use + (if a solution exists).
• For the rest ~30\%~ of test cases, there are no additional constraints.