可爱の星空
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

“当你看向她时，有细碎星辰落入你的眼睛，真好。”——小可爱
在一个繁星闪烁的夜晚，卿念和清宇一起躺在郊外的草地上，仰望星空。
星语心愿，他们，想把这片星空的星星，连成一棵漂亮的树，将这美好的景色记录下来。
现在，天上共有n颗星星，编号分别为1,2.....n，一开始任何两个点之间都没有边连接。
之后，他们两个想在在(u,v)之间连无向边，需要付出|u联通块大小-v联通块大小|的代价。
他们两个想用最少的代价来使这n个点联通，所以他们想知道最小代价是多少。
(多组数据

输入描述:

第一行一个正整数，表示数据组数T

接下来T行每行一个正整数，表示询问的n

输出描述:

T行，每行一个数表示答案
示例1

输入

复制 
1
5

输出

复制 
2

说明

1,2....5五个点，连边顺序为(1,2),(3,4),(1,5),(5,3),代价为0,0,1,1，总代价为2，是n=5的时候最优答案。

虽然(1,2),(2,3),(3,4),(4,5)也可以，但是代价为0,1,2,3，总代价为6，比2大。

备注:

对于20%的数据，T<=2,n<=10

对于40%的数据，T<=10,n<=1000

对于60%的数据，T<=100000,n<=100000

对于另外40%的数据，T=1,n<=1000000000000