ヤギェウォ大学では、植物がとても愛されていることは誰もが知るところです。私たちはこれまで、木や森、さらにはサボテンに関する問題を何百問も作成してきました！残念ながら、動物に関する問題はそれほど人気がありません。今日は、私たちが動物も愛していることを証明したいと思います。

グラフが「クラゲ（jellyfish）」であるとは、頂点数と辺数が等しい単純な連結無向グラフであることを指します。$n$ 個の頂点を持つクラゲ $J$ が与えられます。頂点の任意の集合 $S \subseteq J$ に対して、すべての $T \subseteq S$ について、$T$ のすべての頂点を含み、かつ $S$ の他のどの頂点も含まないクラゲの連結部分グラフが存在する場合、その $S$ を「素晴らしい集合（awesome subset）」と呼びます。

クラゲ $J$ の素晴らしい集合の最大サイズを求めてください。

入力

入力の最初の行には、テストケースの数 $z$ が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、クラゲの頂点数である整数 $n$ ($3 \le n \le 100\,000$) が含まれます。

続く $n$ 行には、クラゲの辺に対応する2つの整数 $u_i, v_i$ ($1 \le u_i \neq v_i \le n$) がそれぞれ含まれます。与えられたグラフはクラゲであり、どの2頂点間も最大で1本の辺で結ばれていることが保証されています。

すべてのテストケースにおける頂点数の合計は $10^6$ を超えません。

出力

各テストケースについて、クラゲの素晴らしい集合の最大サイズを表す整数を1行で出力してください。

入出力例

入力 1

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

出力 1

4
3