P6857 Dreams within Dreams and No More Dreams

Amazing John had a dream, and in that dream he dreamed many dreams. He remembers that the best dream is having no more dreams.

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?

**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 a total of $T$ lines. For each test case, output one positive integer $ans$, meaning the maximum rest points that can be obtained.

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. |Subtask|Test Points|Constraints|Score| -|-|-|-| |$1$|$1\sim2$|$n \le 6, T = 3$|$30$| |$2$|$3\sim5$|$n \le 10^9, T \le 10^5$|$70$| For a subtask, you can get its score if and only if you pass all test points in that subtask. Translated by ChatGPT 5