Q22: 2n-2 Bishops

Given a N by N chess board, we can place at most 2N-2 Bishops on it. E.g.

And that is the best we can do, since there are 2N-1 forward diagonals, but the first and last forward diagonals are opposite squares, and can only contain one bishop between the two.

Given N (up to 14), we can count how many different ways can we put down the 2N-2 bishops so that they do not attack each other? To simplify things, reflections and rotations count as different ways. (e.g. the two boards shown are different.)

To make things interesting though, let us mark one of the positions BAD (B), which prevent us from putting a bishop on it. Given N and a bad square, how many ways can we put down 2N-2 non-attacking bishops?

Submit this problem in the judge as "Q22"

INPUT

There will be multiple test cases. The first line will contain an integer numCase equal to the number of test cases.
For each test case, the there will be a line containning three integers N x y. N is described above. x and y is the coordinate of the bad square (0 <= x <= N-1, 0 <= y <= N-1)

OUTPUT

For each test case, output the number of ways to put 2N-2 bishops down that satisfies the problem statement.

Sample Input

4
2 0 0
2 0 1
3 0 0
3 1 1

Sample Output

2
2
4
8