타원 모양의 땅이 주어져 있는데, 그 땅의 테두리에 n개의 점을 임의로 선택한다. 그리고 나서 각 점들을 다른 모든 점과 직선으로 연결하면 n(n-1)/2 개의 선이 만들어진다. 이 때 테두리 위의 점을 잘 선택해서 나뉘어지는 땅의 개수가 최대가 되도록 만들면 몇 개의 조각으로 나눌 수 있을까? 다음은 n = 6 일 때 땅을 나눠놓은 모습이다.
http://online-judge.uva.es/p/v102/p10213.jpg

파일의 첫번째 줄에는 테스트 케이스를 나타내는 0 보다 크고 3,511 보다 작은 정수 s가 입력된다. 그 다음 줄부터 s 개의 줄에 걸쳐서 0 이상, 2³¹ 미만의 정수 n이 입력된다.

각 테스트 케이스에 대해 n개의 점을 이은 직선에 의해 나뉘는 땅의 최대 개수를 출력한다. 한 줄에 하나씩의 결과만 출력한다.

{{| 4
1
2
3
4 |}}

{{| 1
2
4
8 |}}

----
문제분류 경시대회준비반