SP204 SLEEP - Sleepwalker

There is a building with flat square roof of size _3 $ ^{k} $ \*3_ $ ^{k} $ and sides parallel to north-south and east-west directions. The roof is covered with square tiles of size _1_ (with a side of length 1), but one of the tiles has been removed and there is a hole in the roof (big enough to fall in). The tiles form a rectangular mesh on the roof, so their positions may be specified with coordinates. The tile at the southwestern corner has coordinates (_1,1_). The first coordinate increases while going eastwards, and the second while going northwards. Sleepwalker wanders across the roof, in each step moving from the tile he is standing on to the adjacent one on the east(E), west(W), south(S), or north(N). The sleepwalker roof ramble starts from the southwestern corner tile. The description of the path is a word d $ _{k} $ built of the letters N, S, E, W denoting respectively a step to the north, south, east and west. For _k = 1_ the word describing the path of sleepwalker is d $ _{1} $ = EENNWSWN For _k = 2_ the word describing the path of sleepwalker is d $ _{2} $ = NNEESWSEENNEESWSEEEENNWSWNNEENNWSW - NNEENNWSWNWWWSSENESSSSWWNENWWSSW - WNENWNEENNWSWN.(See the picture that shows how the sleepwalker would go across a roof of dimension _3\*3_ or _9\*9_.) Generally, if _k>=1_, the description of a sleepwalker's path on the roof of dimension _3 $ ^{k+1} $ \*3 $ ^{k+1} $_ is a word: d $ _{k+1} $ = a(d $ _{k} $ ) E a(d $ _{k} $ ) E d $ _{k} $ N d $ _{k} $ N d $ _{k} $ W c(d $ _{k} $ ) S b(d $ _{k} $ ) W b(d $ _{k} $ ) N d $ _{k} $ where functions **a**, **b** and **c** denote the following permutations of letters specifying directions: ``` a: E->N W->S N->E S->W b: E->S W->N N->W S->E c: E->W W->E N->S S->N ``` E.g. a(SEN)=WNE, b(SEN)=ESW, c(SEN)=NWS. We start observing sleepwalker at the time he stands on the tile of coordinates (_u $ _{1} $ , u $ _{2} $_ ). After how many steps will sleepwalker fall into the hole made after removing the tile of coordinates (_v $ _{1} $ , v $ _{2} $_ )?

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case one integer _k_, _1

The only line of output for each test case should contain the number of steps on the sleepwalker's path to the hole.