Diberikan sebuah pohon tak berakar yang berisi $n$ simpul, dengan setiap simpul memiliki warna yang direpresentasikan oleh bilangan bulat positif $c_i$ untuk simpul ke-$i$.

Misalkan $S$ dan $T$ adalah himpunan simpul pada pohon. Sebuah pasangan terurut $(S, T)$ dianggap valid jika semua kondisi berikut terpenuhi:

• Baik $S$ maupun $T$ adalah himpunan tak kosong;
• Semua simpul di $S$ memiliki warna yang sama, dan semua simpul di $T$ memiliki warna yang sama;
• Subgraf $\text{sub}(S)$ dari himpunan simpul $S$ didefinisikan sebagai subgraf terhubung terkecil dari pohon yang memuat himpunan simpul $S$, dan demikian pula untuk $\text{sub}(T)$. Disyaratkan bahwa $\text{sub}(S)$ dan $\text{sub}(T)$ tidak beririsan, artinya keduanya tidak memiliki simpul atau sisi persekutuan.

Tentukan banyaknya semua pasangan terurut $(S, T)$ yang valid modulo $998244353$. Perlu dicatat bahwa jika $S \neq T$, maka pasangan terurut $(S, T)$ dianggap berbeda dari pasangan terurut $(T, S)$.

Masukan

Soal ini memuat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji:

Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 2 \times 10^5$), yang menyatakan banyaknya simpul pada pohon tak berakar.

Baris kedua berisi $n$ bilangan bulat $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), yang menyatakan warna dari setiap simpul.

$n - 1$ baris berikutnya masing-masing berisi dua bilangan bulat $u, v$ ($1 \le u, v \le n, u \neq v$), yang menyatakan sisi-sisi pohon. Dijamin bahwa $n - 1$ sisi ini membentuk struktur pohon.

Data menjamin bahwa jumlah total $n$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan banyaknya pasangan terurut modulo $998244353$.

Contoh

Contoh Masukan 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

Contoh Keluaran 1

2
54
42