Description
Alexander was a strict king. He asked the army not only had to win but defeat the enemy in the way he wanted. Because of stern discipline, the force he had was fighting and winning repeatedly.
One of training was marching on a grid map. The army was on the northwestern square at first, and he gave some orders to the army. They would move into the southeastern square in the end. Alexander only gave them two types of orders: go east or go south. Then they would move along the direction to the next adjacent square on the map. Since Alexander would boil over when they made any mistake and probably killed somebody, they moved as Alexander’s commands in order to survive.
However, the map was not safe since an ancient wizard set magic traps in some squares. Once the army moved into the trap, all of them would be wiped out. As a wisdom king, Alexander knew which square was not safe so that the force could pass the map without any casualty. You, as a loyal retainer, were asked to count the number of ways to pass through the map.
Input
The first line is an integer T followed by T test cases. Each case will start with two integers N and M represented the number of row and column in a map. The next line is an integer K followed by K positions (ri, ci) in next K lines contained traps on the map.
T < 20 and 1 < N, M < 18
Notice that the first sample input is corresponding to the example above.
Output
For every case, output the case number and the number of way to pass through the map. See sample output for more details.