Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS08JUMP - Interstellar Jumps

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.


Added by:kuszi
Date:2009-03-07
Time limit:0.200s-0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:High School Programming League (thanks to Robert Janczewski)

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.