Today is another peaceful day — Kruskal-chan is in the library struggling with graph theory.

Suddenly, a copy of "A Guide to the Doughnut Planet" fell off the shelf, with a note tucked inside:

"Dear Kruskal-chan, we cordially invite you to the Doughnut Planet to help us calculate $n + m$! You remember all the regional adjacency relationships, right?"

Huh? What, what is this? Has my graph theory ability already spread across the universe?

The inhabitants of the Doughnut Planet live on a doughnut-shaped planet. For ease of management, the Doughnut King has drawn $n$ latitude circles (dotted lines in the figure) and $m$ longitude circles (dashed lines in the figure) on the planet, dividing the surface into $nm$ regions, numbered $1 \sim nm$.

Kruskal was invited to visit the Doughnut Planet. Since she had just learned graph theory, she remembered all the regional adjacency relationships (i.e., which regions are adjacent to each other). Can you help her calculate the value of $n + m$?

Input

The problem contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^5$), representing the number of test cases.

For each test case, the first line contains an integer $k$ ($0 \le k \le 10^5$), representing the total number of regional adjacency relationships.

Following this are $k$ lines, each containing two integers $u, v$, indicating that the region numbered $u$ and the region numbered $v$ are adjacent.

Note: The adjacency relationships are guaranteed to be generated by some $n, m$, but may be given in any order.

It is guaranteed that $\sum k \le 10^5$.

Output

Output $T$ lines, each containing an integer representing the value of $n + m$. If the value of $n + m$ cannot be uniquely determined, output $-1$.

Examples

Input 1

2
1
1 2
9
1 2
2 3
3 1
4 5
5 6
6 4
1 6
2 5
3 4

Output 1

3
5

Note

In the first example, one of $n, m$ is $1$ and the other is $2$; it can be proven that no other possibilities exist.

In the second example, one of $n, m$ is $2$ and the other is $3$; it can be proven that no other possibilities exist.