beecrowd | 3420

Torre de Cartas

Por Edson Alves BR Brazil

Timelimit: 1

Enquanto seu pai assiste ao seriado "House of Cards", Luís resolveu construir sua "torre de cartas": ele começa a estrutura alinhando N pares de cartas, onde cada par forma um V invertido. Em seguida, ele coloca uma carta, no sentido horizontal, apoiada nos topos de cada par de Vs invertidos adjacentes. Em cima das cartas horizontais ele constrói um novo nível da torre, com um par de cartas a menos do que o nível anterior, e prossegue até chegar ao topo, que contém um único par de cartas. A figura abaixo ilustra uma torre com três níveis, que foi construída usando exatamente 15 cartas (a linha pontilhada representa o chão):

beecrowd

Luís deseja construir a maior torre de cartas possível, tendo à sua disposição C cartas. Ajude o garoto escrevendo um programa que receba o valor de C e compute o maior valor possível para N de modo que ele possa construir uma torre completa. Por exemplo, se ele tem C = 10 cartas, ele conseguirá montar uma torre com N = 2 pares de cartas na base (usando um total de 7 cartas, sobrando portanto 3 cartas), mas ele não tem o suficiente para uma torre com N = 3 (a qual, conforme visto na figura, demanda um total de 15 cartas).

Entrada

A primeira linha da entrada contém o número T (1 ≤  ≤ 1000) de casos de teste a serem processados.

Cada caso de teste é representado por uma única linha, contendo o valor de C (2 ≤ C ≤ 1018).

Saída

Para cada caso de teste imprima, em uma linha, o maior valor possível para N de modo que Luís possa construir uma torre completa.

Exemplo de Entrada Exemplo de Saída

3
10
15
1234567890

2
3
28688