graph-2

Chacha bought a new game for you, its called Graph. In the game you are given N number of vertices and an N * N matrix M whose (i,j)^th cell denotes the cost of constructing a bidirectional edge between i and j. It is assured that M[i][j]=M[j][i] and M[i][i]=0 for all i,j  \epsilon  {1, 2, 3, ... N}. Now you have to choose  a subset , S, of vertices and make edges between them such that from every vertex in S you can reach to every other vertex in S. But the total cost of constructing the edges should not be more than W. Now for given N, W, and M you have to print the maximum possible size of S. 

Input:
First line consists of T denoting the number of test cases. 
First line of each test case consists of two space separated integers denoting N and W. Then follow N lines containing N space separated integers denoting the matrix M.

Output:
Print the answer in a new line for each test case.

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 16
1 ≤ W, M[i][j] ≤ 1500  \forall  i, j   \epsilon  {1, 2, 3,...N} 

SAMPLE INPUT
1
3 7
0 1 2
1 0 2
2 2 0

SAMPLE OUTPUT
3

Source: hackerearth | Difficulty: EASY


Solutions: