Description

一层高的卡牌金字塔由2张卡牌组成，二层高的卡牌金字塔由7张卡牌组成，三层高的卡牌金字塔由15张卡牌组成，如下图所示，以此类推。你现在有n张卡牌，你要组成一个最大的金字塔；如果还有卡牌剩余，你又用剩余的卡牌组成最大的金字塔；你重复这个过程，直到不能再组成新的金字塔。那么最后，你共建了几个金字塔呢？

Input

有多组数据。 第一行是一个正整数 t（1<=t<=1000），表示有t组数据； 接下来t行每行一个正整数 n (1<=n<=10​^9​)，表示你有n张卡牌。 保证所有n之和不超过10^9

Output

对于每组数据，输出一个整数，表示答案

Samples

5
3
14
15
24
1

1
2
1
3
0

Note

在第一组样例中，你构成的金字塔高度为：1，卡牌剩余张数为1
在第二组样例中，你构成的金字塔高度为：2,2，卡牌剩余张数为0
在第三组样例中，你构成的金字塔高度为：3，卡牌剩余张数为0
在第四组样例中，你构成的金字塔高度为：3,2,1，卡牌剩余张数为0
在第五组样例中，你构成的金字塔高度为：无，卡牌剩余张数为1