The Painter's Studio is preparing mass production of paintings. Paintings are going to be made with aid of square matrices of various sizes. A matrix of size i consists of 2ⁱ rows and 2ⁱ columns. There are holes on intersections of some rows and columns. Matrix of size 0 has one hole. For i > 0, matrix of size i is built of four squares of size 2^(i-1)*2^(i-1). Look at the following figure:

Both squares on the right side and the bottom-left square are matrices of size i-1. Top-left square has no holes. Pictures are constructed in the following way. First, we fix three non-negative integers n, x, y. Next, we take two matrices of size n, place one of them onto the other and shift the upper one x columns right and y rows up. We place such a pattern on a white canvas and cover the common part of matrices with the yellow paint. In this way we get yellow stains on the canvas in the places where the holes in both matrices agree.

Example

Consider two matrices of size 2.

The upper matrix was shifted 2 columns right and 2 rows up. There are three places where holes agree.

Task

Write a program that for each test case:

Input

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.

There is one integer n, 0 <= n <= 100 in the first line of each test case. This number is the size of matrices used for production of paintings. In the second line there is one integer x and in the third line one integer y, where 0 <= x,y <= 2ⁿ. The integer x is the number of columns and y is the number of rows that the upper matrix should be shifted by.

Output

For each test case your program should produce one line with exactly one integer - the number of stains on the canvas.

Example

Sample input:
1
2
2
2

Sample output:
3