يُعطى لك بيان ثنائي التجزئة (bipartite graph). يحتوي الجزء الأيسر على $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