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 は怠け者なので、追加する通路をできるだけ少なくしたいと考えています。どのように通路を追加しても、Prof. Pang が Prof. Shou を捕まえることができる初期位置のペア $(u, v)$ が必ず存在してしまう場合は、$-1$ を出力してください。

入力

入力の最初の行には、テストケースの数を示す整数 $T$ ($1 \le T \le 10^4$) が含まれます。

各テストケースについて、最初の行には部屋の数を示す整数 $n$ ($2 \le n \le 10^5$) が含まれます。

続く $n - 1$ 行には、部屋 $u$ と部屋 $v$ をつなぐ通路を示す2つの整数 $u$ と $v$ ($1 \le u, v \le n$) が含まれます。

すべてのテストケースにおける $n$ の合計は $2 \times 10^5$ を超えず、部屋と通路は常に木を形成していることが保証されます。

出力

各テストケースについて、追加する通路の最小数を出力してください。もし不可能であれば $-1$ を出力してください。

入出力例

入力 1

2
1 2

出力 1

-1

入力 2

4
1 2
2 3
3 4

出力 2

1

入力 3

4
1 2
2 3
2 4

出力 3

-1

入力 4

5
1 2
2 3
3 4
3 5

出力 4

2