链接: https://cses.fi/problemset/task/3406

板块: Mathematics

时限: 1.00 s ｜ 内存: 512 MB

题目描述

三角形数是指形如 $1+2+\dots+k$ 的正整数。前几个三角形数为 $1$、$3$、$6$、$10$ 和 $15$。

每个正整数都可以表示为若干三角形数之和。例如，$42=21+21$，$1337=1326+10+1$。

给定一个正整数 $n$，确定和为 $n$ 的三角形数的最小个数。

输入

第一行包含一个整数 $t$：表示测试组数。

之后每行包含一个正整数 $n$。

输出

对于每个测试，输出三角形数的最小个数。

数据范围

$1 \le t \le 100$ $1 \le n \le 10^{12}$

样例输入

5
1
2
3
42
1337

样例输出

1
2
1
2
3