تُعطى شجرة غير مجذرة تحتوي على $n$ من العقد، حيث يكون لكل عقدة لون يُمثَّل بعدد صحيح موجب $c_i$ للعقدة ذات الترتيب $i$.

لنفترض أن $S$ و $T$ مجموعتان من العقد في الشجرة. يُعتبَر الزوج المرتب $(S, T)$ صالحاً إذا تحققت جميع الشروط التالية:

• كل من $S$ و $T$ مجموعة غير خالية؛
• جميع العقد في $S$ لها نفس اللون، وجميع العقد في $T$ لها نفس اللون؛
• يُعرَّف الرسم الجزئي $\text{sub}(S)$ لمجموعة العقد $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