#描述#
Crazy Dog ( always be called C.D.) likes to take a walk in a room divided by a N x N square grid (1 < n <= 26). He always starts in the upper left corner of the grid. The grid has empty squares (denoted below by .') and a number (B) of barriers (denoted below by#'). Here is a vivid depiction of a grid including a demonstration of the grid labeled: Crazy travels vertically (up or down) or horizontally (left or right). He can travel either down or right from his starting location, which is always A1. (marked by ‘S’ )

Crazy travels as long as he can when he choose his direction. He stops and turns 90 degrees whenever he encounters the edge of the board or one of the barriers. He can not leave the grid or enter a space with a barrier. Additionally, Crazy can not recross any square he has already visited. He stops his traversal altogether any time he can no longer move.
Here is one sample traversal on the sample grid above (not best ):

Crazy traversed right, down, right, down, left, up, and right. He could not continue since he encountered a square already visited. Things might have gone differently if he had chosen to turn back toward our left when he encountered the barrier at F5.
Your task is to determine and print the largest possible number of squares that C.D. can visit if he chooses his turns wisely. Of course A1 should be considered as one grid visited initially.

#格式#
##输入格式##
The first line of the input contains an integer T (T &lt= 10), indicating the number of cases.
Each test case consists of a line which has N ( 1 &lt= N &lt= 26 ), the size of room, and B, the number of barriers, ( 1 &lt= B &lt= 200 ).The following B lines contain the locations of each barrier. The sample input file below describes the sample grid above.

##输出格式##
For each test case, you should write a single number in a line which represents the maximum grids C.D. can visit.

#样例1#
##样例输入1##

1
8 4
E2
A6
G1
F5

##样例输出1##

33

#限制#
1000ms
32768KB

#提示#

#来源#
dyh