KMOVES - Knight Moves

no tags 

A knight is located at the (black) origin of an infinite chessboard. Let f(n) define the number of black squares the knight can reach after making exactly n moves. Given n (0 <= n <= 108), output f(n).

Input

The first line of the input contains a single integer T, the number of test cases (1 <= T <= 106). Each test case consists of a single positive integer n.

Output

For each value of n in the input, print a single line containing.

Example

Input:
2
0
1

Output:
1
0

hide comments
omar alkattan: 2012-07-13 00:56:29

dear mostafa 36a2 you've been terminated B)

Mostafa 36a2: 2012-07-09 02:33:41

How To Be Faster than 0.07 ???!

Last edit: 2013-01-18 15:24:28
Alrezza Pradanta BB: 2012-07-06 21:40:30

Just found out this problem. :)

marwan akkad: 2012-07-06 17:56:57

Could anybody explain the output

Fernando Fonseca [ITA]: 2012-07-06 04:28:25

This was left unsolved for 2 years, suddenly I solve it and everybody wants to join in the fun? :)

Mostafa 36a2: 2012-06-26 17:54:04

Thanks GOD

Last edit: 2012-07-09 02:39:08
Mostafa 36a2: 2012-06-26 17:51:21

الحمد لله
أول كود صحيح لي بعد
TEST
الحمد لله


Added by:Amlesh Jayakumar
Date:2009-12-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 PERL6
Resource:Own