Blocks

問題文

天野さんは、ブロックを使って網野さんにIQテストを出題することにしました。このテストは、三次元空間上に積み上げられた立方体のブロックの個数を、ある一点からの視点のみで網野さんに当てさせるクイズです。

天野さんは網野さんをできるだけ困らせるため、限られたブロックをうまく配置することでなるべく難しくしたいです。

各マスが3つの正の整数の組 $(x,y,z)$ で表される三次元のグリッドがあります。各マスにはブロックを1個置くことができ、初めはどのマスにもブロックは置かれていません。

天野さんは、ちょうど $N$ 個のマスにブロックを置くことができます。ただし、マス $(x,y,z)$ にブロックを置く場合、 $z \ge 2$ ならばマス $(x,y,z-1)$ にもブロックが置かれていなければなりません。

達成可能な以下の条件すべてを満たすマス $(x,y,z)$ の最大の個数を求めてください。

• マス $(x,y,z)$ にブロックが存在する。
• マス $(x',y,z)$ にブロックが存在するような $x' > x$ を満足する $x'$ が存在する。
• マス $(x,y',z)$ にブロックが存在するような $y' > y$ を満足する $y'$ が存在する。
• マス $(x,y,z')$ にブロックが存在するような $z' > z$ を満足する $z'$ が存在する。

例えば、N = 31のとき、このようにブロックを配置すると、12マスが条件を満たします。

なお、この置き方が最適であるとは限りません。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1 \le T \le 10^5$
• $0 \le N \le 10^{18}$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

各テストケース $\mathrm{case}_t ~ (1 \leq t \leq T)$ は以下の形式で与えられる。

出力

$T$ 行出力せよ。 $t$ 行目には $t$ 番目のテストケースについての答えを出力せよ。

サンプル 1

入力

3
8
100
1000000000000000000 

出力

2
66
999998349036962257

一つ目のテストケースについて、 $N=8$ のとき、例えば以下のような置き方をすることで、条件を満足するマスが最大になります。

また、以下のような置き方でも、条件を満足するマスが最大になります。