F. Создание уровней
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иван разрабатывает свою собственную компьютерную игру. Сейчас Иван хочет создать все уровни игры. Но перед этим он хочет нарисовать каждый уровень на бумаге в виде графа.

Иван решил, что в графе i-го уровня должно быть ровно ni вершин, а сам граф должен быть неориентированный. Главная, по мнению Ивана, характеристика графа — количество специальных рёбер, называемых мостами. Ребро, соединяющее вершины u и v, называется мостом, если оно лежит на каждом пути из u в v (и эти вершины окажутся в разных компонентах связности, если ребро стереть). Иван хочет, чтобы в построенном для каждого уровня графе как минимум 50% всех рёбер были бы мостами. Также Иван хочет максимизировать количество рёбер в каждом графе.

Итак, задание, которое вам дал Иван, состоит в следующем: по заданным q числам n1, n2, ..., nq для каждого i определить максимальное количество рёбер в графе из ni вершин, если хотя бы 50% рёбер должны быть мостами. Обратите внимание, в графах не может быть петель или кратных рёбер.

Входные данные

В первой строке записано число q (1 ≤ q ≤ 100 000) — число графов, которые нужно построить Ивану.

Затем следуют q строк, в i-й из них записано число ni (1 ≤ ni ≤ 2·109) — количество вершин в i-м графе.

Обратите внимание, что во взломах вы можете использовать только q = 1.

Выходные данные

Выведите q чисел, i-е из которых равно максимальному количеству рёбер в i-м графе.

Пример
Входные данные
3
3
4
6
Выходные данные
2
3
6
Примечание

В примере из условия можно построить следующие графы:

  1. 1 - 2, 1 - 3;
  2. 1 - 2, 1 - 3, 2 - 4;
  3. 1 - 2, 1 - 3, 2 - 3, 1 - 4, 2 - 5, 3 - 6.