Кішкентай Көгілдір Балықта $n$ төбесі бар $G = (V, E)$ ағашы бар. Ағаштың төбелері $1$-ден $n$-ге дейінгі оң бүтін сандармен нөмірленген. $i$-ші ($1 \le i \le n - 1$) қабырға $u_i$ және $v_i$ төбелерін қосады.

Кішкентай Көгілдір Балық сізден әрбір $i$ төбесіне келесі талаптарды қанағаттандыратындай $1$-ден $n$-ге дейінгі оң бүтін $p_i$ санын меншіктеуді сұрайды:

• Әрбір $1 \le i < j \le n$ үшін $p_i \neq p_j$. Басқаша айтқанда, $p_{1 \dots n}$ ұзындығы $n$ болатын орын алмастыруды құрайды.
• Ағаштағы әрбір $(u, v) \in E$ қабырғасы үшін $p_u + p_v \le n + 1$ орындалады.

Кішкентай Көгілдір Балық сізден осы шартты қанағаттандыратын қанша $p$ орын алмастыруы бар екенін есептеуді сұрайды. Әдеттегідей, бұл есеп Not a Work of Idol болғандықтан, Кішкентай Көгілдір Балық сіздің жауапты үлкен жай сан модулі бойынша шығарғаныңызды қаламайды. Сондықтан жауапты $4$ модулі бойынша шығарыңыз.

Input

Бірнеше тест жағдайлары бар. Кірістің бірінші жолында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жағдайы үшін кірістің бірінші жолында ағаштағы төбелер санын білдіретін бүтін сан $n$ ($1 \le n \le 10^6$) берілген.

Келесі $(n - 1)$ жолдың әрқайсысында $u_i$ және $v_i$ төбелерін қосатын қабырғаны білдіретін екі бүтін сан $u_i$ және $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) берілген. Осы $(n - 1)$ қабырға дұрыс ағаш құрайтынына кепілдік беріледі.

Барлық тест жағдайлары бойынша $n$ сандарының қосындысы $10^6$-нен аспайтынына кепілдік беріледі.

Output

Әрбір тест жағдайы үшін $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