TJANDRA2  Tjandra 19th birthday present (HARD)
The 07 February 2013 was Tjandra's 19th birthday,
I want to make a present to him and all other great SPOJ solvers by the way.
So I set this HARD puzzle problem extension of the yet good
TJANDRAS.
Warning : To solve the 'easy' task, you need a O(N^0.5) algorithm,
but to solve this 'harder' task, you need something around O(N^0.34),
so it's not about optimization tricks!!!
Please note that I checked my data with my 'semibruteforce'O(N^0.5)Python3solution and it took me 16 hours.
Don't forget to have fun with that problem!
The Game
This game/puzzle is about matches, given N matches, your task is to arrange the matches (not necessarily all) such that the number of rectangles (any size) is maximum.
Input
The input begins with the number T of test cases in a single line.
In each of the next T lines there are one integer N.
Output
For each test case, on a single line, print the required answer (maximum number of rectangles).
Example
Input: 6 3 4 8 12 15 987654321123456789 Output: 0 1 3 9 12 60966316127114768913148159571503206
Constraints
1 < T ≤ 100 1 < N ≤ 10^18
The T numbers N are uniformrandomly chosen in the range.
Explanations
First test case:
No rectangle can be formed with only 3 matches.
Second test case:
Only one rectangle can be formed with 4 matches.
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 matches formation:
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:
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:
Sixth test case:
You have to figure by yourself how to compute that in the required time.
hide comments
milosm:
20190516 10:47:19
please give me solution


Min_25:
20140305 17:37:42
@Francky : Thank you.


Francky:
20140305 17:25:01
Congratulations to Min_25 who successfully find the last 'little' secret to take 1st place. ;) It's the secret for fast AC in easy edition !!! 

Michael Kharitonov:
20130307 17:53:47
Yes! AC! Good hard problem!


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130220 08:32:51
@Francky: Thanks a lot for making this hard problem with my name as the title, haha :D But sorry I can't enjoy this problem for now because my limited ability (and, don't worry, I promise someday, I'll solve this problem)... Wow, you patient enough to wait 16 hours to check your case, haha ;) And unbelievable, that "TJANRAS" was designed as easy as possible, I expected it will have many solver enjoyed it, but in fact, that problem only have 6 solvers until now.. strange.. the same condition happen to my "A_W_S_N" problem too.. (unlike you, I like if my problem has many solver, haha :D, just kidding :P I'll very proud of myself if I can solve your great problem :))


Francky:
20130219 17:30:45
@tjandra : Sorry to give your present so lately, I had a whole week out of the Net.

Added by:  Francky 
Date:  20130219 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource: 