Problem Statement: Find the Number of States

You are given ‘n’ cities, some of which are connected by bidirectional roads. You also have an ‘n x n’ matrix ‘roads’, where if city ‘i’ and city ‘j’ are connected by a road, then ‘roads[i][j] = 1’. Otherwise, ‘roads[i][j] = 0’.

A state is defined as a group of cities that are connected to each other and share no connections with cities outside of this group. Two cities ‘i’ and ‘j’ are connected if city ‘j’ is reachable from city ‘i’ using a sequence of roads.

Your task is to determine the number of such states.

Input:

The first line of the input consists of an integer ‘T’, indicating the number of test cases. Each test case consists of:

- A single integer ‘n’, the number of cities.

- An ‘n x n’ matrix ‘roads’ with n lines, where each line consists of n space-separated integers.

Output:

For each test case, output the number of states determined from the matrix. The result for each test case should be on a new line.

Example:

Input:
n = 4
roads = [ [1, 1, 1, 0],
           [1, 1, 1, 0],
           [1, 1, 1, 0],
           [0, 0, 0, 1] ]

Output:
2

In this example, there are two states.

Constraints:

• 1 <= T <= 10
• 1 <= n <= 100
• Value in each element of ‘roads’ = {0, 1}
• Time limit: 1 second

Note:

- A city is connected to itself, so for every city ‘i’, ‘roads[i][i] = 1’.