该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个神奇的一天，蜡笔小新和妈妈来到超市，发现他最爱的小新之友饼干在打折，在小新的恳求下妈妈答应他可以买 $n$ 个小新之友饼干
打折规则如下： 现有一个兔子数列即 数列的第一个和第二个数都为 $1$，接下来每个数都等于前面 $2$ 个数之和
如 $1，1，2，3，5，8 ，...$
现超市根据这个数列买指定数量来减免，数列前三项的价格不变，从满足第四项的数量开始依次减 $(i-3)$ 元，如满三盒减免 $1$ 元 ，满五盒减免 $2$ 元，满八盒减免 $3$ 元，依次类推，减免金额无法累计。 $i$ 表示这个数是兔子序列第 $i$ 项
现在小新想要用最少的钱买到恰好 $n$ 个小新之友饼干，请你告诉他最多减免多少钱， 可以吗，求求了呜呜呜，小新在这里谢谢大家了。

Ps: 保证 $n$ 一定属于这个数列

输入格式

输入 $T$ $\left ( 1\le T\le 10^{4} \right )$ 组数据
对于每组数据
输入 $n$ $\left ( 1\le n\le 10^{9} \right )$代表需要购买的小新之友饼干个数

输出格式

对于每组数据输出 最多减免

样例

2
1
3

0
1