The City of Karpeydi

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Instant Commute Planning Corporation (ICPC) is the contractor of a project in the city of Karpeydi:

The city of Karpeydi has a number of buildings, between some of which exist streets. Each one of these streets is specified by a number in the range of [0, 1], which represents the chance of heavy traffic in it. The chance of traffic in each street is independent of all other streets. Building a is accessible from building b if there exists a path between a and b with its chance of free-flowing traffic greater than or equal to a constant p (in the range of (0, 1]). We need to choose the least number of buildings from the city of Karpeydi and place ambulances in them, so that we have access to all buildings in the city in order to be able to send an ambulance as fast as possible to any building in case of fire.

Input

The input contains several test cases.

In the first line of input comes T (0 < T < 16), the number of test cases.

For each test case, the first two lines contain n ≤ 25 and 0 < p ≤ 1 representing the number of buildings and the least chance of free-flowing traffic between two buildings respectively. In each of the next n lines, you are given n numbers in the range of [0, 1], the number in row i and column j specifying the chance of heavy traffic between buildings i and j (and vice versa). If this number equals one, it means that the street is always jammed - or in fact does not exist. Assume the precision of each chance to be at most 103, i.e. each number is represented by at most 3 decimal places.

Output

For each test print one number which specifies the least number of buildings that need to be chosen for placing the ambulances.

Sample Input

2
5 0.5
0.000 0.2 1.0 1.0 0.6
0.2 0.000 0.2 0.5 1.0
1.0 0.2 0.000 1.0 0.6
1.0 0.5 1.0 0.000 1.0
0.6 1.0 0.6 1.0 0.000
9 0.6
0.000 0.4 1.0 1.0 0.5 1.0 1.0 0.3 1.0
0.4 0.000 1.0 0.3 1.0 1.0 1.0 1.0 1.0
1.0 1.0 0.000 0.4 1.0 1.0 1.0 1.0 1.0
1.0 0.3 0.4 0.000 0.15 1.0 1.0 1.0 1.0
0.5 1.0 1.0 0.15 0.000 0.29 0.2 1.0 1.0
1.0 1.0 1.0 1.0 0.29 0.000 0.4 1.0 1.0
1.0 1.0 1.0 1.0 0.2 0.4 0.000 0.3 1.0
0.3 1.0 1.0 1.0 1.0 1.0 0.3 0.000 0.1
1.0 1.0 1.0 1.0 1.0 1.0 1.0 0.1 0.000

Sample Output

2
2

Submit

Source: 13th Iran Nationwide Internet Contest - UT