{"raw_statement":[{"iden":"statement","content":"Old Macdonald wants to build a new hen house for his hens. He buys a new rectangular area of size N by M. The night before he builds the hen house, snake Rana devises an evil plan to plant bombs in K distinct cells in the area to kill the hens and eat them for dinner later.\n\nThe morning of, Old Macdonald notices that each of the K cells, where snake Rana planted a bomb, have a marking on them. That won’t stop him though, all he must do is build the hen house in an area with no bombs.\n\nAssume that rows are numbered from top to bottom, and columns are numbered from left to right. Old Macdonald now wants to know the number of ways he can choose sub-rectangles of top left coordinates (x1, y1) and bottom right coordinates (x2, y2) (x1 ≤ x2) (y1 ≤ y2) such that there are no bombs in the sub rectangle.\n\nThe first line of input is T – the number of test cases.\n\nThe first line of each test case is three integers N, M, and K (1 ≤ N, M ≤ 104) (1 ≤ K ≤ 20).\n\nThe next K lines each contains distinct pair of integers x, y (1 ≤ x ≤ N) (1 ≤ y ≤ M) - where (x, y) is the coordinate of the bomb.\n\nFor each test case, output a line containing a single integer - the number of sub-rectangles that don’t contain any bombs.\n\n"},{"iden":"input","content":"The first line of input is T – the number of test cases.The first line of each test case is three integers N, M, and K (1 ≤ N, M ≤ 104) (1 ≤ K ≤ 20).The next K lines each contains distinct pair of integers x, y (1 ≤ x ≤ N) (1 ≤ y ≤ M) - where (x, y) is the coordinate of the bomb."},{"iden":"output","content":"For each test case, output a line containing a single integer - the number of sub-rectangles that don’t contain any bombs."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case:  \n- Let $ N, M \\in \\mathbb{Z}^+ $ denote the dimensions of the grid ($ 1 \\leq N, M \\leq 10^4 $).  \n- Let $ K \\in \\mathbb{Z}^+ $ denote the number of bombs ($ 1 \\leq K \\leq 20 $).  \n- Let $ B = \\{ (x_i, y_i) \\mid i \\in \\{1, \\dots, K\\} \\} \\subseteq \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ be the set of bomb coordinates.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified} $  \n2. $ 1 \\leq N, M \\leq 10^4 $  \n3. $ 1 \\leq K \\leq 20 $  \n4. All bomb coordinates in $ B $ are distinct.\n\n**Objective**  \nFor each test case, compute the number of sub-rectangles defined by top-left $ (x_1, y_1) $ and bottom-right $ (x_2, y_2) $ with $ 1 \\leq x_1 \\leq x_2 \\leq N $, $ 1 \\leq y_1 \\leq y_2 \\leq M $, such that no bomb lies inside the rectangle:  \n$$\n\\left| \\left\\{ (x_1, y_1, x_2, y_2) \\in \\{1, \\dots, N\\}^2 \\times \\{1, \\dots, M\\}^2 \\,\\middle|\\, x_1 \\leq x_2,\\, y_1 \\leq y_2,\\, B \\cap \\left( [x_1, x_2] \\times [y_1, y_2] \\right) = \\emptyset \\right\\} \\right|\n$$","simple_statement":"Given an N×M grid with K bombs at distinct positions, count how many sub-rectangles contain no bombs.","has_page_source":false}