Friend Circle Counter

You are given a social network represented by an adjacency matrix. Each cell in the matrix is a character '1' or '0', where '1' indicates that two people are direct friends and '0' indicates they are not.

Your task is to determine the number of friend circles in the network. A friend circle is a group of people who are directly or indirectly connected via friendship. Note that every person is a friend with themselves.

The input begins with an integer T representing the number of test cases. For each test case, the first line contains an integer n representing the number of people. The following n lines each contain a string of length n which represents the friendship relations of that person with every other person.

Hint: Two people belong to the same friend circle if there exists a path (a chain of friendships) connecting them.

Formula: The number of friend circles can be computed by performing a depth-first search (DFS) on the graph. If we let \(G=(V,E)\) be the graph where \(V\) is the set of people and \(E\) is the set of friendship relationships, then the answer is the number of connected components in \(G\).

inputFormat

The first line of input contains an integer T (1 ≤ T ≤ 100) representing the number of test cases.

Each test case is described as follows:

• The first line contains an integer n (1 ≤ n ≤ 200), the number of people.
• The following n lines each contain a string of length n, consisting only of the characters '0' and '1', which describes the friendship matrix. The j-th character in the i-th string is '1' if person i is friends with person j and '0' otherwise.

outputFormat

For each test case, output a single integer on a new line indicating the number of friend circles in the network.

## sample

1
1
1

1

</p>