Құрамында $n$ төбесі бар түбірсіз ағаш берілген, мұнда әрбір төбенің түсі бар және $c_i$ оң бүтін саны $i$-ші төбенің түсін білдіреді.

$S$ пен $T$ ағаштағы төбелер жиындары болсын. Егер төмендегі шарттардың барлығы орындалса, $(S, T)$ реттелген жұбы жарамды деп есептеледі:

• $S$ те, $T$ де бос емес жиындар;
• $S$ жиынындағы барлық төбелердің түсі бірдей және $T$ жиынындағы барлық төбелердің түсі бірдей;
• $S$ төбелер жиынының $\text{sub}(S)$ ішкі графы ағаштың $S$ төбелер жиынын қамтитын ең кіші байланысқан ішкі графы ретінде анықталады, $\text{sub}(T)$ үшін де дәл солай. $\text{sub}(S)$ пен $\text{sub}(T)$ қиылыспауы талап етіледі, яғни олардың ортақ төбелері немесе қырлары болмауы керек.

Барлық жарамды $(S, T)$ реттелген жұптарының санын $998244353$ модулі бойынша анықтаңыз. Егер $S \neq T$ болса, онда $(S, T)$ реттелген жұбы $(T, S)$ реттелген жұбынан өзгеше болып саналатынын ескеріңіз.

Кіріс

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

Әрбір тест жағдайы үшін:

Бірінші жолда түбірсіз ағаштағы төбелер санын білдіретін $n$ ($1 \le n \le 2 \times 10^5$) бүтін саны берілген.

Екінші жолда әр төбенің түсін білдіретін $n$ бүтін сан $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$) берілген.

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

Деректер барлық тест жағдайлары бойынша $n$ мәндерінің жалпы қосындысы $2 \times 10^5$ шамасынан аспайтынына кепілдік береді.

Шығыс

Әрбір тест жағдайы үшін реттелген жұптар санын $998244353$ модулі бойынша білдіретін бір бүтін саннан тұратын жалғыз жолды шығарыңыз.

Мысал

Мысал кіріс 1

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

Мысал шығыс 1

2
54
42