丢丢陈要周游世界,现在有 nnn 个他想去的城市。旅行的唯一费用是通行费。从第 iii 个城市到第 jjj 个城市的通行费为 (i+j) mod (n+1)(i+j)\ mod\ (n+1)(i+j) mod (n+1)。缴纳通行费后 i,ji,ji,j 两个城市可以相互到达,并且再次通过这两座城市是不需要缴费。求丢丢陈周游世界的最小费用。丢丢陈可以从任意一座城市开始旅行,在任意一座城市结束旅行。
其中,modmodmod 为取余运算符,a mod ba\ mod\ ba mod b 的结果为 aaa 除 bbb 后的余数,例如 10 mod 3=110\ mod\ 3 = 110 mod 3=1。
第一行仅有一个数字 T(1≤T≤10)T(1\leq T\le 10)T(1≤T≤10) 代表数据组数。下面依次是每一组数据
每组数据仅有一行一个个整数 n(1≤n≤105)n(1\le n \le 10^5)n(1≤n≤105) 代表城市数目。
每组数据输出一行一个数字,表示最小费用。
2 2 10
0 4