Prof. Pang i Prof. Shou lubią grać w grę w berka.

Mapa gry składa się z $n$ pokoi i $n - 1$ dwukierunkowych kanałów. Mapa gry jest spójna, co oznacza, że tworzy drzewo.

Na początku Prof. Pang znajduje się w pokoju $u$, a Prof. Shou w pokoju $v$ ($u \neq v$). Prof. Pang i Prof. Shou wykonują ruchy na zmianę, przy czym Prof. Shou wykonuje ruch jako pierwszy. W swojej turze gracz zna swoje położenie oraz położenie drugiego gracza i może zdecydować, czy pozostać w obecnym pokoju, czy przejść do innego pokoju, który jest bezpośrednio połączony kanałem z obecnym pokojem. Kiedy Prof. Pang i Prof. Shou znajdują się w tym samym pokoju, Prof. Shou zostaje złapany przez Prof. Panga.

Prof. Pang i Prof. Shou są bardzo inteligentni. Prof. Pang chce złapać Prof. Shou w skończonej liczbie ruchów. Prof. Shou nie chce zostać złapany przez Prof. Panga w żadnej skończonej liczbie ruchów.

Prof. Shou męczy się byciem łapanym za każdym razem i prosi o pomoc Prof. Fei. Prof. Shou prosi Prof. Fei o dodanie pewnych kanałów tak, aby Prof. Pang nie mógł go złapać w skończonej liczbie ruchów dla żadnej pary początkowych pokoi $(u, v)$. Prof. Fei jest leniwy, więc ma nadzieję dodać jak najmniej kanałów. Jeśli niezależnie od sposobu dodania kanałów zawsze istnieje para pokoi $(u, v)$, dla której Prof. Pang może złapać Prof. Shou, wypisz $-1$.

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T \le 10^4$) oznaczającą liczbę zestawów danych.

Dla każdego zestawu danych, pierwsza linia zawiera pojedynczą liczbę całkowitą $n$ ($2 \le n \le 10^5$) oznaczającą liczbę pokoi.

W kolejnych $n - 1$ liniach każda linia zawiera dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le n$) oznaczające kanał łączący pokój $u$ z pokojem $v$.

Gwarantuje się, że suma $n$ we wszystkich zestawach danych nie przekracza $2 \times 10^5$, a pokoje i kanały zawsze tworzą drzewo.

Wyjście

Dla każdego zestawu danych wypisz liczbę oznaczającą najmniejszą liczbę dodanych kanałów lub wypisz $-1$.

Przykład

Wejście 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

Wyjście 1

-1
1
-1
2