The Computer Game#376
John and Brus are playing a military strategic game on the computer. The game is played on a flat world map. At the beginning of the game, Brus chooses positions for his army, and then John must choose strategic points for his army according to the following rules:
Each strategic point must be a lattice point (a lattice point is a point with integer coordinates) such that |x| + |y| < N;
John can choose any number of strategic points;
All strategic points must be distinct;
Each strategic point must be free (i.e., not occupied by Brus's army);
Each pair of different strategic points must be connected (possibly via other strategic points).
Two different lattice points (x_1, y_1) and (x_2, y_2) are connected if |x_1 - x_2| + |y_1 - y_2| = 1. If , , and are strategic points, and and are connected, and are connected, then and are also connected.
The first line contains a single integer — the number of test cases. Each test case starts with a line containing two integers and separated by a single space. is the number mentioned in the first rule. is the number of lattice points on the map already occupied by Brus's army. Each of the next lines contains two integers X_k and Y_k separated by a space. Each point (X_k, Y_k) is occupied by Brus's army.
For each test case, print a single line containing the number of ways John can choose strategic points for his army.
Constraints
1 \leq T \leq 74
1 \leq N \leq 7
1 \leq M \leq 225
-7 \leq X_k, Y_k \leq 7
All (X_k, Y_k) will be distinct.
Example 1