נתון עץ לא מכוון וללא שורש המכיל $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