We are given an integer k and an arithmetic expression E with the operations '+', '-', and arguments from the set {0,1,...,9}. Is it possible to put some parentheses in E to get a new expression E' whose value equals k? If the answer is positive what is the minimum number of pairs of parentheses '(', ')' that are necessary?

Illustration

It is sufficient to put one pair of parentheses in the expression 5 - 4 + 5 to get an expression with value -4, namely 5 - (4 + 5) = -4.

Task

Write a program that for each data set from a sequence of several data sets:

Input

The first line of the input file contains one positive integer d not larger than 10. This is the number of data sets. The data sets follow. Each set of data occupies two consecutive lines of the input file. The first line contains two integers n and k, 2 <= n <= 40, -180 <= k <= 180. The even integer n is the length of E. The second line contains the expression itself written as a string of length n. The string contains operators '+' or '-' in odd positions and numbers from the set {0,1,...,9} in even positions.

Output

For each i = 1,...,d, your program should write to the i-th line of the output file one word 'NO' if the i-th input expression cannot be transformed into any expression of value k, and the smallest number of pairs of parentheses necessary otherwise.

Example

Sample input:
5 
6 -4 
+5-4+5 
2 1 
+1 
4 1 
-1+1 
4 0 
-1+1 
4 -2 
-1+1 

Sample output:
1 
0 
NO 
0 
1