Сізге екі үлесті граф берілген. Сол жақ бөлігі 1-ден $n_1$-ге дейін нөмірленген $n_1$ төбеден тұрады, ал оң жақ бөлігі 1-ден $n_2$-ге дейін нөмірленген $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$ төбесінің арасында қыр бар екенін білдіретін екі бүтін $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$) сандары берілген.

Еселі қырлар жоқ екеніне, сондай-ақ $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