大家都知道在亞捷隆大學（Jagiellonian University），我們非常熱愛植物。我們已經出過數百道關於樹、森林甚至仙人掌圖的題目！遺憾的是，關於動物的題目並不那麼受歡迎。今天，我們想證明我們也同樣熱愛動物。

我們稱一個圖為「水母圖」（jellyfish），如果它是一個頂點數與邊數相等的簡單連通無向圖。給定一個具有 $n$ 個頂點的水母圖 $J$。對於頂點的任意子集 $S \subseteq J$，如果對於每一個 $T \subseteq S$，都存在一個 $J$ 的連通子圖，該子圖包含 $T$ 中的每一個頂點，且不包含 $S$ 中的任何其他頂點，則稱 $S$ 為一個「極佳子集」（awesome subset）。

請問 $J$ 的極佳子集的最大可能大小是多少？

輸入格式

輸入的第一行包含測試案例數量 $z$。接著是各個測試案例的描述。

每個測試案例的第一行包含一個整數 $n$ ($3 \le n \le 100\,000$)，代表水母圖的頂點數量。

接下來的 $n$ 行，每行包含兩個整數 $u_i, v_i$ ($1 \le u_i \neq v_i \le n$)，對應水母圖的邊。保證給定的圖是一個水母圖，且任意兩個頂點之間最多只有一條邊相連。

所有測試案例的頂點總數不超過 $10^6$。

輸出格式

對於每個測試案例，輸出一行，包含一個整數，代表該水母圖極佳子集的最大可能大小。

範例

輸入 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