15 1 s 128 MB

John and Brus are going to a theater to see a very interesting movie. They would like to have seats next to each other in the same row. The theater contains **n** rows, with **m** seats in each row. Rows are numbered 1 to **n** from front to back, and seats are numbered 1 to **m** from left to right. Some of the seats are already reserved, but John and Brus can book any of the available seats.

You are given int[]s **row** and **seat**. The i-th elements of **row** and **seat** are the row number and seat number of the i-th reserved seat. All remaining seats are available. Print the number of ways for John and Brus to book two available seats next to each other in the same row.

The first line of the input gives the number of test cases, T (1 <= **T** <= 500).

For each test case, the first line contains a positive integer **n** and **m**, which will be between 1 and 1,000,000,000, inclusive.

The second line contains a positive integer **p**, the number of elements in **row** and **seat**, no more than 47.

The third line contains **p** integers representing int[] **row** where each element will be between 1 and **n**, inclusive.

The fourth line contains **p** integers representing ints[] **seat** where each element will be between 1 and **m**, inclusive.

All pairs (**row**[i], **seat**[i]) will be distinct.

For each test case, print the number of ways for John and Brus to book two available seats next to each other in the same row, in one line.

## Sample Input | ## Sample Output |
---|---|

4 2 3 2 1 2 2 3 2 3 6 1 1 1 2 2 2 1 2 3 1 2 3 4 7 1 1 1 10 8 10 1 9 6 10 6 7 9 3 9 2 7 7 3 3 7 1 5 1 6 2 | 1 0 23 54 |