Hilbert is a game in which you control a robot on an infinite two‐dimensional grid. There are three

commands available to you:

• G: Go one square forward in the current direction.

• L: Turn ninety degrees counterclockwise.

• R: Turn ninety degrees clockwise.

After playing this game for a while, you wonder how many squares you can reach within a certain

number of moves. **Write a program to calculate the answer to this question.**

Input

On the first line an integer t (1<= t <=100): the number of test cases. Then for each test case one line

comes with an integer