Tout le monde sait qu'à l'Université Jagellonne, nous aimons beaucoup les plantes. Nous avons créé des centaines de problèmes sur les arbres, les forêts et même les cactus ! Malheureusement, les problèmes sur les animaux ne sont pas aussi populaires. Aujourd'hui, nous voulons prouver que nous aimons aussi les animaux.

Nous disons qu'un graphe est une méduse (jellyfish) s'il s'agit d'un graphe simple, connexe et non orienté ayant un nombre égal de sommets et d'arêtes. On vous donne une méduse $J$ avec $n$ sommets. Pour un sous-ensemble arbitraire de sommets $S \subseteq J$, nous disons que $S$ est un sous-ensemble génial (awesome subset) si, pour tout $T \subseteq S$, il existe un sous-graphe connexe de la méduse qui contient chaque sommet de $T$ et ne contient aucun autre sommet de $S$.

Quelle est la taille maximale possible d'un sous-ensemble génial de $J$ ?

Entrée

La première ligne de l'entrée contient le nombre de cas de test $z$. Les descriptions des cas de test suivent.

La première ligne de chaque cas de test contient un entier $n$ ($3 \le n \le 100\,000$) — le nombre de sommets de la méduse.

Les $n$ lignes suivantes contiennent deux entiers $u_i, v_i$ ($1 \le u_i \neq v_i \le n$) chacune, correspondant aux arêtes de la méduse. Il est garanti que le graphe donné est une méduse, et que deux sommets quelconques sont reliés par au plus une arête.

Le nombre total de sommets dans tous les cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un seul entier : la taille maximale possible d'un sous-ensemble génial de la méduse.

Exemples

Entrée 1

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

Sortie 1

4
3