SP13829 TJANDRA2 - Tjandra 19th birthday present (HARD)

2013年2月7日是Tjandra的19岁生日，我想为他和其他优秀的SPOJ解题者准备一份礼物。因此，我设计了这个极具挑战性的拼图题，它是[TJANDRAS](http://www.spoj.com/problems/TJANDRAS/)问题的升级版。**注意：** 为了解决“简单”版本，你需要一个时间复杂度为 $O(N^{0.5})$ 的算法，而面对这个“更难”的版本，需要大约 $O(N^{0.34})$ 的算法，所以这并不仅仅是优化技巧的问题！需要指出的是，我使用一种“半暴力”的 $O(N^{0.5})$ Python3方案检验了我的数据，花了16小时。记得在解决问题的过程中享受其中的乐趣！

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行中，每行给出一个整数 $N$。

对于每个测试用例，输出一行表示对应的答案，即矩形的最大数量。

$$1 \le T \le 10^5, \quad 1 \le N \le 10^9$$ **本翻译由 AI 自动生成**