Петя решил открыть свой боулинг-клуб с необычными упражнениями. В данный момент ему не хватает лишь кегель.
В боулинге есть два типа упражнений, которые задаются следующими расстановками кегель:
- треугольник: в первом ряду стоит $$$1$$$ кегля, в каждом следующем ряду стоит на одну кеглю больше;
- прямоугольник: стоящие кегли образуют заполненный прямоугольник со длинами сторон строго больше $$$1$$$.
Примеры для треугольника из $$$4$$$ рядов и прямоугольников из $$$2$$$ рядов по $$$5$$$ кегель и $$$3$$$ рядов по $$$5$$$ кегель:
Петя хочет купить такое количество кегель, что из них можно будет составить как треугольник, так и прямоугольник, и ни в одном из упражнений не останется лишних кегель. Длины сторон прямоугольника должны быть строго больше $$$1$$$.
Определите максимальное количество кегель, которые Петя может купить, если его бюджета хватит не более чем на $$$c$$$ кегель. Если Петя не может купить столько кегель, что и треугольник, и прямоугольник с длинами сторон больше $$$1$$$, собираются без лишних кегель, то выведите 0.
Во входных данных будут заданы несколько тестовых наборов. Для каждого из них необходимо решить задачу независимо.
В первой строке следует целое число $$$t$$$ ($$$1 \le t \le 1\,000$$$) — количество тестовых наборов.
В каждой из следующих $$$t$$$ строк следует по одному целому числу $$$c$$$ ($$$1 \le c \le 10^{18}$$$).
Выведите $$$t$$$ целых чисел, причем $$$i$$$-е число должно быть равно максимальному количеству кегель, которые может купить Петя в $$$i$$$-м тестовом наборе.
Если для некоторого тестового набора Петя не может купить столько кегель, что и треугольник, и прямоугольник можно собрать без лишних кегель, то выведите 0 для этого тестового набора.
3
10
16
2
10
15
0
Подробно рассмотрим пример, в котором заданы $$$3$$$ тестовых набора.
В первом тестовом наборе $$$c = 10$$$. На первых двух картинках в условии изображено, что можно собрать и треугольник, и прямоугольник, которые состоят ровно из $$$10$$$ кегель.
Во втором тестовом наборе $$$c = 16$$$. В этом случае можно собрать корректный прямоугольник из $$$16$$$ кегель ($$$4$$$ ряда по $$$4$$$ кегли или же $$$2$$$ ряда по $$$8$$$ кегель), однако треугольник из $$$16$$$ кегель собрать невозможно. Прямоугольник для $$$15$$$ кегель изображен на третьей картинке в условии, треугольник из $$$15$$$ кегель собрать также можно, он будет состоять из $$$5$$$ рядов.
В третьем тестовом наборе $$$c = 2$$$. В этом случае невозможно собрать как корректный прямоугольник (одна из его сторон будет равна $$$1$$$), так и корректный треугольник, поэтому ответ 0.
