Problem 6 : Connected Components

Problem

Consider an undirected graph G formed from a large number of nodes connected by edges. G is said to be connected if there exists a path between any two distinct nodes in the graph. For example, consider the graph given below

The above graph is no connected, because there is no path from node A to node node D. However, it has two connected components, {A,B,C} and {D,E}. A connected component is a subset of nodes of the graph, such that there is a path between any two nodes in this subset, and no path to any node which is not in this set.

In this problem, you are required to determine the number of connected components of a given graph.

Input

The first line of the input contains n, the number of test cases. It is then followed by n test cases. The first line of the input contains a single upper case alphabet, representing the largest node name in the graph, followed by the number of edges in the graph. Each successive line contains a pair of upper case letters, denoting an edge in the graph.

Output

For each test case, output the number of connected components in the graph.

Sample Input

2
E 4
AB
CE
DB
EC
E 4
AB
CE
DB
EC

Sample Output

2
2