시노카의 그래픽스 공부

시노카는 정다각형으로 만든 모델을 삼각형으로 나누어 렌더링하려 한다. 각 정다각형을 겹치지 않는 삼각형으로 나눌 때 필요한 삼각형의 개수를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

$A_i$는 $i$번째 정다각형의 정점 개수이다.

각 케이스마다 $N$개의 줄에 각 정다각형을 나누는 삼각형의 개수를 입력 순서대로 출력한다.

• $1\leq T\leq100\,000$.
• $1\leq N\leq100\,000$.
• $3\leq A_i\leq10^9$.
• 모든 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.