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$ 出发，沿 $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$ |
对于一个子任务，你能获得它的分数当且仅当你通过了其中所有的数据点。