נתון לכם גרף דו-צדדי. החלק השמאלי מכיל $n_1$ קודקודים הממוספרים מ-1 עד $n_1$, והחלק הימני מכיל $n_2$ קודקודים הממוספרים מ-1 עד $n_2$. ישנן $m$ קשתות, שכל אחת מהן מחברת קודקוד אחד משמאל לקודקוד אחד מימין.

עבור כל קטע $[l, r]$ בצד ימין (כאשר $1 \le l \le r \le n_2$), נתבונן בתת-הגרף המתקבל על ידי:

• השארת כל הקודקודים השמאליים $1, 2, \dots, n_1$;
• השארת הקודקודים הימניים שהאינדקסים שלהם נמצאים ב-$[l, r]$ בלבד;
• השארת הקשתות ששני קצותיהן נשמרו בלבד.

בתת-גרף זה, חשבו את גודלו של שידוך מקסימלי (המספר המקסימלי של קשתות זרות זו לזו). נסמן ערך זה ב-$f(l, r)$.

עליכם לחשב את הערך הבא:

$$\sum_{1 \le l \le r \le n_2} f(l, r) \cdot l \cdot r \cdot ((l \oplus r) + 1),$$

כאשר $\oplus$ מציין את פעולת ה-XOR הביטית.

הדפיסו את ערך הסכום הזה מודולו $998\,244\,353$.

קלט

הקלט מכיל מספר מקרי בדיקה.

השורה הראשונה מכילה מספר שלם יחיד $T$ ($1 \le T \le 2000$), מספר מקרי הבדיקה.

עבור כל מקרה בדיקה, השורה הראשונה מכילה שלושה מספרים שלמים $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), המייצגים את מספר הקודקודים משמאל, מספר הקודקודים מימין ומספר הקשתות.

כל אחת מ-$m$ השורות הבאות מכילה שני מספרים שלמים $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), המציינים שיש קשת בין הקודקוד השמאלי $u$ לקודקוד הימני $v$.

מובטח שאין קשתות מקבילות, ושסכום ה-$n_1$ וסכום ה-$n_2$ אינם עולים על $5000$.

פלט

עבור כל מקרה בדיקה, הדפיסו שורה אחת המכילה מספר שלם אחד — הסכום הנדרש מודולו $998\,244\,353$.

דוגמה

קלט

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

פלט

81
529
12
81