이분 그래프가 주어집니다. 왼쪽 부분은 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$ ($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