Description

Niuniu has a cake, and he wants to share it with children. The cake is initially a circle. Niuniu will choose $n$ distinct points on the circumference and connect every pair of these points with a line segment. These segments will divide the cake into several pieces.

Now, Niuniu wants to know the maximum number of pieces the cake can be divided into. Please output the answer.

Input Format

The input contains up to $20$ lines. Each line contains an integer $n$, as described in the “Description”. It is guaranteed that $0 \le n \le 64$.

Output Format

Answer each query in order. For each query, output one line containing an integer representing the answer.

2
3
4

2
4
8

Hint

Sample Explanation

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Resources such as solutions can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5