## 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}

**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}### Example

There are sleepwalker's paths on roofs of dimension * 3*3* and * 9*9* on the
picture below. In the second case, the point at which the observation starts and the hole have
been marked. The sleepwalker has exactly * 20* steps to the hole (from the
moment the observation starts).

### Task

Write a program which:

- reads from the standard input integer
*k*denoting the size of the roof (*3*), the position of the sleepwalker at the moment the observation starts and the position of the hole,^{k}*3^{k} - computes the number of steps that the sleepwalker will make before he falls into the hole,
- writes the result to the standard output.

### Input

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<=k<=60*, denoting the size of the roof (*3 ^{k}*3^{k}*) is written. In
each of the following two lines of the test case two natural
numbers

*x, y*separated with a space are written,

*1<=x<=3^k*,

*1<=y<=3^k*. The numbers in the second line are the coordinates of the tile the sleepwalker is standing on. The numbers in the third line are the coordinates of the hole. You may assume, that with these data the sleepwalker will eventually fall into the hole after some number of steps.

### Output

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

### Example

Sample input:1 2 3 2 7 2Sample output20

Added by: | Piotr Ćowiec |

Date: | 2004-09-13 |

Time limit: | 7s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS PERL6 VB.NET |

Resource: | 6th Polish Olympiad in Informatics, stage 2 |