Prof. Pang 和 Prof. Shou 喜歡玩追逐遊戲。

遊戲地圖由 $n$ 個房間和 $n - 1$ 條雙向通道組成。遊戲地圖是連通的，這意味著地圖形成了一棵樹。

起初，Prof. Pang 在房間 $u$，而 Prof. Shou 在房間 $v$ ($u \neq v$)。Prof. Pang 和 Prof. Shou 輪流行動，由 Prof. Shou 先手。在每一回合中，玩家知道自己和對手的位置，並可以決定留在當前房間，或移動到與當前房間有通道直接相連的另一個房間。當 Prof. Pang 和 Prof. Shou 位於同一個房間時，Prof. Shou 就會被 Prof. Pang 抓住。

Prof. Pang 和 Prof. Shou 都非常聰明。Prof. Pang 希望在有限的回合內抓住 Prof. Shou。Prof. Shou 則希望永遠不被 Prof. Pang 抓住。

Prof. Shou 對每次都被抓住感到厭倦，於是找 Prof. Fei 幫忙。Prof. Shou 請 Prof. Fei 新增一些通道，使得對於任何初始房間對 $(u, v)$，Prof. Pang 都無法在有限的回合內抓住他。Prof. Fei 很懶，所以他希望新增的通道數量越少越好。如果無論如何新增通道，總存在一對房間 $(u, v)$ 使得 Prof. Pang 可以抓住 Prof. Shou，則輸出 $-1$。

輸入格式

第一行包含一個整數 $T$ ($1 \le T \le 10^4$)，表示測試資料的組數。

對於每組測試資料，第一行包含一個整數 $n$ ($2 \le n \le 10^5$)，表示房間的數量。

接下來的 $n - 1$ 行，每行包含兩個整數 $u$ 和 $v$ ($1 \le u, v \le n$)，表示連接房間 $u$ 和房間 $v$ 的通道。

保證所有測試資料中 $n$ 的總和不超過 $2 \times 10^5$，且房間和通道始終形成一棵樹。

輸出格式

對於每組測試資料，輸出一個數字，表示需要新增的最少通道數量，若無法達成則輸出 $-1$。

範例

輸入格式 1

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

輸出格式 1

-1
1
-1
2