High School Programming League Problems Archive

Input

It is well known, that the MathUniverse is full of strange places. One of them is the Strange Jumps Galaxy (SJG). In it, there exists an unusual means of communication called a "strange jump". But strange jumps are possible only between some pairs of planets (possibly placed in different parts of SJG).

All pairs of planets between which a strange jump is possible have been inventoried. If it is possible to make a strange jump from planet number x to planet number y, then this is denoted as (x,y), where x and y are integers from the range {0, 1, …, 999}.

If jumps (x,y) and (y,z) are possible, we can talk about a sequence of strange jumps (with this particular sequence of jumps you visit three planets, but longer sequences are also possible).

Your task is to compute the maximum number of planets you can visit during the one sequence of strange jumps. You can assume that apart from the "trivial jump": (x, x), there does not exist a sequence of jumps that allows you to come back to the same planet from which the sequence started.

Input

The first line consists of a single number t - the number of test cases. In the next t lines you are given a single test cases in each line. Each test case is in the form of a set of pairs of planets (no more then 100 000 pairs in each set).

Output

For each of the t test cases, print in a separate line one number denoting the maximum number of planets possible to visit in a single jump series.

Example

Input:
3
(0,0)
(0,1) (0,2) (0,0) (1,1) (2,2)
(1,1) (0,1) (1,2) (3,3) (1,3) (0,0) (2,2) (0,2) (0,3)
Output:
1
2
3

Scoring

There will be 5 tests. Each test will be worth two points, to form a total of 10 points.