คุณได้รับกราฟสองส่วน (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