Little Cyan Fish memiliki sebuah pohon $G = (V, E)$ dengan $n$ verteks. Verteks-verteks pada pohon tersebut dinomori dengan bilangan bulat positif dari $1$ hingga $n$. Sisi ke-$i$ ($1 \le i \le n - 1$) menghubungkan verteks $u_i$ dan $v_i$.

Little Cyan Fish ingin Anda menetapkan sebuah bilangan bulat positif $p_i$ dari $1$ hingga $n$ pada setiap verteks $i$, yang memenuhi persyaratan berikut:

• Untuk setiap $1 \le i < j \le n$, berlaku $p_i \neq p_j$. Dengan kata lain, $p_{1 \dots n}$ membentuk sebuah permutasi dengan panjang $n$.
• Untuk setiap sisi $(u, v) \in E$ pada pohon, berlaku $p_u + p_v \le n + 1$.

Little Cyan Fish ingin Anda menghitung berapa banyak permutasi $p$ yang memenuhi kondisi ini. Seperti biasa, karena masalah ini adalah Not a Work of Idol, Little Cyan Fish tidak ingin Anda mengeluarkan jawaban modulo bilangan prima yang besar. Oleh karena itu, silakan keluarkan jawaban modulo $4$.

Input

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat tunggal $T$ ($1 \le T$), yang menyatakan jumlah kasus uji.

Untuk setiap kasus uji, baris pertama dari masukan berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^6$), yang menyatakan jumlah verteks pada pohon.

Sebanyak $(n - 1)$ baris berikutnya masing-masing berisi dua bilangan bulat $u_i$ dan $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), yang menyatakan sebuah sisi yang menghubungkan verteks $u_i$ dan $v_i$. Dijamin bahwa $(n - 1)$ sisi ini membentuk sebuah pohon yang valid.

Dijamin bahwa jumlah dari $n$ di seluruh kasus uji tidak melebihi $10^6$.

Output

Untuk setiap kasus uji, keluarkan satu baris yang berisi satu bilangan bulat, yang menyatakan jawaban modulo $4$.

Examples

Input 1

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

Output 1

1
2
0
2