Description

Amazing John wants to make a problem based on his dreams.

Amazing John had $n$ dreams. Between every pair of dreams, there is exactly one bridge directly connecting them, and no bridge connects a dream to itself.

By crossing a bridge $e_{u,v}$, you can go from dream $u$ to dream $v$, or from $v$ to $u$, and gain $1$ rest point.

For every bridge $e_{u,v}$, it can only be crossed once, no matter whether you cross it forward or backward.

When you arrive at a dream and all bridges connected to it can no longer be crossed, Amazing John will stop dreaming.

Now Amazing John is very sleepy. He wants to know: starting from any dream, what is the maximum number of rest points he can obtain?

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, meaning there are $T$ test cases.

Next are $T$ lines. Each line contains a positive integer $n$, meaning he had $n$ dreams.

Output Format

Output a total of $T$ lines.

For each test case, output one positive integer $ans$, meaning the maximum rest points that can be obtained.

1
3

3

Hint

Sample explanation:

Start from $1$, go along $e_{1,2}$ to reach $2$, then along $e_{2,3}$ to reach $3$, and finally along $e_{3,1}$ to reach $1$.

In total, you gain $3$ rest points.

For a subtask, you can get its score if and only if you pass all test points in that subtask.

Translated by ChatGPT 5