梦中梦与不再有梦

题目背景

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

1
3

输出样例 #1

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