梦中梦与不再有梦

Amazing John 做了一个梦，梦到他做了很多梦。 记得最好的梦，是不再有梦。

Amazing John 想要以自己的梦出一道题。 Amazing John 做了 $n$ 个梦。每两个梦之间都有且仅有一条桥梁直接相连，不会有桥梁从一个梦连向自身。 通过桥梁 $e_{u,v}$ 可以从梦 $u$ 到达 梦 $v$ 或从 $v$ 到达 $u$ ，并且获得 $1$ 点休息值。 对于每个桥梁 $e_{u,v}$ ，它只能被经过一次，无论是正向经过还是反向经过。 当到达一个梦且与它相连的所有桥梁都不能经过时， Amazing John 就会结束他的做梦。 现在 Amazing John 很困，他想知道从任意一个梦出发，最多可以获得多少休息值？

**本题有多组数据。** 第一行包含一个正整数 $T$ ，表示有 $T$ 组数据。 接下来有 $T$ 行，每行包含一个正整数 $n$ ，表示他做了 $n$ 个梦。

输出共 $T$ 行。 对于每组数据，输出一行一个正整数 $ans$ ，表示最多可以获得的休息值。

1
3

3

样例解释： 从 $1$ 出发，沿 $e_{1,2}$ 到达 $2$ ，再沿 $e_{2,3}$ 到达 $3$ ，最后沿 $e_{3,1}$ 到达 $1$。 总共获得了 $3$ 点休息值。 |子任务|数据点|数据范围|分数| -|-|-|-| |$1$|$1\sim2$|$n≤6,T=3$|$30$| |$2$|$3\sim5$|$n≤10^9,T≤10^5$|$70$| 对于一个子任务，你能获得它的分数当且仅当你通过了其中所有的数据点。