Bridges and Tunnels

On some days the campus is very wet, on others very cold; there are days when everyone would rather stay indoors. To make that possible, the campus designers have gradually connected the buildings with tunnels and bridges. A connection is sometimes built together with a building and sometimes added later. Because the network is not always complete, it may still be impossible to move between two buildings without going outside.

Each time a new bridge or tunnel is built between two buildings, report how many buildings can be reached from it without ever going outside — that is, the number of buildings in the connected group that the new connection now belongs to.

The first line contains a single integer: the number of test cases that follow.

Each test case begins with a line containing an integer $n$ ($n \le 100000$), the number of bridges or tunnels that will be built. All buildings already exist, but at the start of a test case no bridge or tunnel has been built yet. The next $n$ lines list the connections in the order they are built; each line contains the names of the two buildings being connected, separated by a space. A building name is a string of up to 20 uppercase or lowercase letters, and names are case-sensitive.

For every bridge or tunnel that is built, print a line with a single integer: the number of buildings that can be reached from that connection without going outside (the size of its connected group right after the connection is added).