TJANDRA2 - Tjandra 19th birthday present (HARD)

no tags 

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 'semi-brute-force'-O(N^0.5)-Python3-solution 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 uniform-randomly 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:
Case 3 - Fig

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 - Fig

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 - Fig

Sixth test case:
You have to figure by yourself how to compute that in the required time.


hide comments
milosm: 2019-05-16 10:47:19

please give me solution
=(Francky)=> solution

Last edit: 2019-06-11 22:07:43
Min_25: 2014-03-05 17:37:42

@Francky : Thank you.
I enjoyed this problem and the secret. :)

Francky: 2014-03-05 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: 2013-03-07 17:53:47

Yes! AC! Good hard problem!
--ans--> Congratulations, you solved it exactly in the way it was designed for. I now hope other great solvers will come take a chance.
Edit : In fact, there's a specific room of this problem (not the factorization part, we can always do better) that you ignored, it boosts seriously the easy edition ! My secret : I used C++ for 'nth_element' in order to find the median of the thing.

Last edit: 2013-03-09 18:22:29
(Tjandra Satria Gunawan)(曾毅昆): 2013-02-20 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 :-))
--ans--> In fact it's not so hard, and I know you have all the knowledge to solve this task. Good luck to everybody.
EDIT(Tjandra): Ok, let's wait for other user comments :-P

Last edit: 2013-02-20 09:24:06
Francky: 2013-02-19 17:30:45

@tjandra : Sorry to give your present so lately, I had a whole week out of the Net.
@all others : good luck, the hell is again inside this task!!!


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