Memento Mori

장 교수에게 모든 원소가 0인 $n \times m$ 행렬이 있다. 장 교수는 이 행렬의 $k$개 원소를 1로 바꾼다.

$1, 2, 3, 4$의 순열 $p_1, p_2, p_3, p_4$가 주어졌을 때, 장 교수는 다음 조건을 모두 만족하는 부분 행렬의 개수를 구하려 한다.

• 부분 행렬에 들어 있는 1의 개수가 정확히 4개이다.
• 부분 행렬에서 1의 위치를 $(r_1, c_1), (r_2, c_2), (r_3, c_3), (r_4, c_4)$라 하자. 이때 $r_1 < r_2 < r_3 < r_4$이고, 모든 $1 \le i < j \le 4$에 대해 $(p_i - p_j) \cdot (c_i - c_j) > 0$이다.
• 선택한 부분 행렬 안에 위 두 조건을 만족하는 다른 부분 행렬이 없다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 행렬의 크기 $n$, $m$과 1의 개수 $k$가 주어진다 ($1 \le n, m, k \le 2000$). 둘째 줄에는 순열 $p_1, p_2, p_3, p_4$가 주어진다. 이어서 $k$개의 줄에 $i$번째 1의 위치 $r_i$, $c_i$가 주어진다 ($1 \le r_i \le n$, $1 \le c_i \le m$). 같은 위치에 두 개 이상의 1이 주어지지 않는다.

테스트 케이스는 최대 250개이며, 전체 입력 크기는 최대 250 KiB이다.

각 테스트 케이스마다 조건을 모두 만족하는 부분 행렬의 개수를 한 줄에 출력한다.