TJANDRAS - Tjandra 19th birthday (EASY)

This day (7 February 2013) is my 19th birthday Laughing So, I want to celebrate it on SPOJ by making this EASY puzzle problem.

This game/puzzle is about matches, given n matches, your task is to arrange the matches (not necessarily all) such that number of rectangle (any size) is maximum.

Input

First line there is an integer T100 then T lines follow, each line contain an integer n<1.000.000.000.

Output

For each test case, output required answer (maximum number of rectangles)

Example

Input:
5
3
4
8
12
15

Output:
0
1
3
9
12

Explanation

-->First test case: No rectangle can be formed with only 3 matches

-->Second test case: Only one rectangle can be formed with 4 mathes

-->Third test case:

there are max 3 rectangles (2 size 1x1, 1 size 2x1) can be formed with number of matches<=8, here is one of the mathes formation:

Case 3

-->Fourth test case:

there are max 9 rectangles (4 size 1x1, 2 size 2x1, 2 size 1x2, 1 size 2x2) can be formed with number of matches <=12, here is one of the formation:

case 4

-->Fifth test case:

there are max 12 rectangles (5 size 1x1, 3 size 2x1, 1 size 3x1, 2 size 1x2, 1 size 2x2) can be formed with number of matches <=15, here is one of the formation:

case 5

Information

Time limit≈150x my program speed, Enjoy this birthday party game, I set this problem such that semi naive solution will pass..

See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2013-02-07
Time limit:3.263s
Source limit:19000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Just Watch This Video! I Uploaded it 1 year ago

hide comments
2013-02-08 14:47:18 praveen123
Happy Birthday !!!
2013-02-07 22:04:27 abdelkarim
happy birthday Tjandra !! .

this is a message for you
take this input for this problem :D .
but clear '\n'
1
13 13
110010111110111100101100100010011110011101001011010011
000000001100010000001110001000000011000000000000100010
000000000010000000011000110100000100000010100100001010
0010011
http://www.spoj.com/problems/GNY07D/

Last edit: 2013-02-08 15:33:10
2013-02-07 18:57:34 (Tjandra Satria Gunawan)(曾毅昆)
@all: Thanks :-D
2013-02-07 17:48:03 c[R]@zY f[R]0G
Happy birthday, Tjandra!!
2013-02-07 09:07:12 Francky
I wish you the best for the coming year ; happy birthday, speedy Tjandra.
2013-02-07 08:00:15 Ikhaduri
Happy birthday, man :)
2013-02-07 07:07:53 Ehor Nechiporenko
Happy birthday, Tjandra!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.