| Codeforces Round 671 (Div. 2) |
|---|
| Закончено |
Джет устала после уничтожения города и хочет отдохнуть. Она любит высоты, поэтому для отдыха ей надо забраться повыше, и для этого она решила делать лесенки.
Лесенка является клетчатой фигурой, состоящей из одинаковых квадратных клеточек. Если лесенка состоит из $$$n$$$ ступенек, то это означает, что такая лесенка состоит из $$$n$$$ столбиков, первый имеет высоту $$$1$$$ клетку, второй имеет высоту $$$2$$$ клетки, $$$\ldots$$$, $$$n$$$-й имеет высоту $$$n$$$ клеток. Нижние клетки всех столбиков должны находятся в одной строке.
Лесенка, имеющая $$$n$$$ ступенек, называется красивой, если ее можно покрыть $$$n$$$ непересекающимися квадратами. Все квадраты должны состоять целиком из клеточек лесенки.
Скажите Джет, какое максимальное количество различных красивых лесенок она может построить, используя суммарно не больше $$$x$$$ клеточек. Ни одна клеточка не может быть использована больше одного раза.
В первой строке входных данных содержится одно целое число $$$t$$$ $$$(1 \le t \le 1000)$$$ — количество наборов входных данных.
Единственная строка описания каждого набора входных данных содержит единственное целое число $$$x$$$ $$$(1 \le x \le 10^{18})$$$ — количество клеточек для постройки лесенок.
Для каждого набора входных данных выведите единственное число — максимальное количество различных красивых лесенок, которые можно построить, используя суммарно не больше $$$x$$$ клеточек.
4 1 8 6 1000000000000000000
1 2 1 30
В первом наборе входных данных можно построить только одну лесенку, состоящую из $$$1$$$ ступеньки. Она является красивой. Поэтому ответ равен $$$1$$$.
Во втором наборе входных данных можно построить две различные красивые лесенки: из $$$1$$$ ступеньки и из $$$3$$$ ступенек. На это уйдёт $$$7$$$ клеточек. В таком случае останется еще одна клеточка, но из нее уже нельзя сделать ни одной красивой лесенки такого размера, которого еще нет. Поэтому ответ равен $$$2$$$.
В третьем наборе входных данных можно построить только одну из двух красивых лесенок: с $$$1$$$ ступенькой или с $$$3$$$ ступеньками. В первом случае останется $$$5$$$ клеточек, из которых можно сделать только лесенку из $$$2$$$ ступенек. Она не является красивой, а Джет строит только красивые лесенки. Поэтому в данном случае ответ $$$1$$$. Если же Джет построит лесенку с $$$3$$$ ступеньками, то у неё не останется ни одной клеточки. В этом случае ответ тоже $$$1$$$.
