시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 256 MB0000.000%

문제

По прямоугольному клеточному полю, состоящему из n столбцов и m строк, путешествует робот. Он может начать свое путешествие в любой клетке первой строки. Далее он может совершить некоторое (возможно, нулевое) количество ходов. Пусть робот стоит в столбце x и строке y, тогда за один ход он может перейти либо в клетку (x + 1, y + 1), либо в клетку (x - 1, y + 1). Конечно, робот не может выходить за границы поля.

Путешествие робота осложняется тем, что на поле есть прямоугольные преграды, стороны которых параллельны сторонам поля. Робот не может пойти в клетку, которая покрывается преградой. Никакие две преграды не пересекаются, но могут касаться.

Вам необходимо посчитать количество клеток, в которые может попасть робот.

입력

В первой строке задано число T — количество тестов. Далее следует описание T тестов.

В первой строке теста дано два целых числа n и m (1 ≤ nm ≤ 109) — количество столбцов и строк на поле. В следующей строке задано одно целое число k (1 ≤ k ≤ 105) — количество преград на поле. В следующих k строках задано описание преград. Каждая такая строка состоит из четырех целых чисел x1y1x2y2, обозначающих координаты противоположных углов преграды (1 ≤ x1 ≤ x2 ≤ n, 2 ≤ y1 ≤ y2 ≤ m). Гарантируется, что преграды не пересекаются.

Общее количество преград во входном файле не превышает 105.

출력

Для каждого из T тестовых примеров выведите одно число — количество клеток, которые может посетить робот.

예제 입력 1

1
5 7
3
2 2 4 2
1 3 1 5
2 5 3 6

예제 출력 1

14