SP13829 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](http://www.spoj.com/problems/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 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.

For each test case, on a single line, print the required answer (maximum number of rectangles).