Problem Of The Week (4/10/2009)

Popular Friend

Problem Statement

You want to find the most popular person in a social network (orkut, for example). To do this, you will count the number of "M-friends" that each person has. Person A is called an M-friend of another person B if they are friends with each other or if there exists some person C who is a friend of both A and B. The most popular person is the person with the highest number of M-friends. (There might be more than one if multiple people all have the maximal number of M-friends).

Input

The first line in input will contain an integer T. T test cases follow. In each test case first line consists of an integer S, denoting the size of the social network. Then S lines follow, each containing S characters (making a complete SxS matrix, call it friends[][]). Each character is either 'N' or 'Y'.

If the ith character of the jth line is 'Y' this means i and j are friends (hence jth character of ith line will also be 'Y').

Output

Output a single integer P for each case representing the number of M-friends of the most popular person in this social network.




Constraints

• 1<=S<=50

Sample

Input

5
3
NNN
NNN
NNN
3
NYY
YNY
YYN
5
NYNNN
YNYNN
NYNYN
NNYNY
NNNYN
10
NNNNYNNNNN
NNNNYNYYNN
NNNYYYNNNN
NNYNNNNNNN
YYYNNNNNNY
NNYNNNNNYN
NYNNNNNYNN
NYNNNNYNNN
NNNNNYNNNN
NNNNYNNNNN
15
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNYNNNNNNN
NNNNNNNYNNNNNNY
NNNNNNNNNNNNNNY
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNYYNNNNNNNNNNN
NNNNNYNNNNNYNNN
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNNNNNNNNNNNNNN
YNNYYNNNNYNNNNN

Output
 

0
2
4
8
6

Explanations:

1. Here, there are 3 people and none of them are friends, so everybody has zero M-friends.
2. Each person has two M-friends.
3. Persons 0 and 4 have two M-friends, persons 1 and 3 have three M-friends. Person 2 is the most popular one - four M-friends.

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.