#1769 볼록 다각형의 삼각분할

165  1 s   128 MB  

Description

3D 엔진 프로그래머의 꿈을 갖고 있는 신입생 Noname은 공간상의 다각형을 Polygon이라고 부르는 삼각형으로 분할하여 표현할 수 있다는 것을 선배로부터 듣게 되었다.

이미지 출처 :  http://www.codersources.net , OpenGL tutorial 7 
 
모든 과정은 첫 걸음부터 시작해야 하는 법. 복잡한 공간상의 기하학적 데이터를 다루기에 앞서 Noname은 일단 평면상의 볼록 다각형을 삼각형으로 분할하는 작업을 수행해 보기로 했다. 그런데 신입생 Noname은 수능이 끝난 다음 중고등학교에서 배웠던 내용을 모두 잊어버리고 말아 선배인 당신에게 볼록 N-다각형이 최대 몇개의 삼각형으로 분할될 수 있는지 문의하기로 했다.
 
취업준비에 시간이 촉박한 선배인 당신은 볼록 N-다각형이 최대 몇 개의 삼각형으로 분할되는지 매번 가르쳐주는 대신, 이에 대한 정답을 가르쳐 주는 프로그램을 작성해 주기로 한다. ( 단, 분할된 삼각형은 서로 겹칠 수 없으며, 또한 각 삼각형은 볼록 N-다각형의 꼭지점을 연결하는 선분으로만 분할될 수 있다.)

Input

입력은 여러개의 테스트 케이스로 이뤄지면 입력의 첫 줄에는 테스트 케이스의 개수 $T$ 가 주어진다. $( 1 \leq T \leq 100)$

각 테스트 케이스는 한줄에 정수 하나로 이뤄져 있으며, 이는 볼록 $N$-다각형의 $N$을 뜻한다. $( 0 \leq N \leq 1, 000 )$

Output

볼록 $N$-다각형이 최대 몇 개의 서로 겹치지 않는 삼각형으로 분할될 수 있는지 출력하도록 한다. 단, 삼각형이 단 1개 이상으로 구성될 수 없을 때, 즉, 다각형이 구성되지 않을 때는 -1을 출력하도록 한다.

Sample Input

Sample Output

3
3
5
2
1
3
-1

Source

2011 Ajou University Programming Contest, Division 2