Description

Since Prefect rescue GF from xx last time successfully,GF has fell in love with him.GF wants to do something in return, but she's very shy, don't want to be direct,
After all, she is a girl.Then she comes up with a good idea,she plans to give Perfect a problem.if Perfect can solve it,GF will give him kiss.

Now the problem coming,give you an string which only contains 0, 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9.You are asked to add the sign ‘+’ or ’-’ between the characters. 
Just like give you a string “12345”, you can work out a string “123+4-5”. 
Now give you an integer N,how many ways can you find to make the result of the string equal to N .
You can only choose at most one sign between two adjacent characters.

If Perfect find a way,then GF give him a kiss.Perfect want get kiss as much as possible,Can you tell him the maximum kiss he can get.
If Perfect can't find a way exactly,GF also give him a kiss as encouragement.

Input

The first line contain a integer T,meaning T test cases.
Each case contains a string s and a number N . You may be sure the length of the string will not exceed 20 and the absolute value of N will not exceed 999999999999.

Output

The output contains one line for each data set : the the maximum kiss he can get.

Sample Input

2
123456789 3
21 1
 

Sample Output

18
1

HINT

Source

NBU