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

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

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