SP174 PAINTTMP - Paint templates

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 _$ ^{i} $_ rows and 2 _$ ^{i} $_ 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.

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

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