Description

gsy是个有强迫症的人，所以他希望自己每天花的钱或者攒的钱都比前一天多一块钱！

也就是第一天gsy会赚一块钱或者花一块钱，第二天gsy会赚两块钱或者花两块钱。

当然如果有一天gsy的钱不够花了，他就会去贷款，因为他决定了要花钱，那就必须得有钱！所以gsy的钱有可能是负数（表示他欠银行钱）

为了防止gsy乱花钱，花椰妹给gsy定下了一个规则，如果gsy可以在某一天攒够正好 n 元钱（注意是正好 n 元钱），那花椰妹就给gsy介绍一个女朋友！

注意这里的 n 可能是负数，表示gsy正好欠银行 n 元钱

钱和女朋友哪个更重要？那当然是都重要！

所以gsy希望知道自己最快在第几天可以攒够正好 n 元钱，请你帮帮他

Input

输入第一行包含一个整数 T，表示测试数据数量 对于每组测试数据，输入一行包含一个整数 n，含义如题

Output

对于每组测试数据输出一行，表示gsy最快在第几天结束以后能攒够正好 n 元钱

Samples

1
2

3

Limitation

对于 40% 的数据，|n| <= 100 对于 100% 的数据，|n| <= 10^9 1s, 1024KiB for each test case.