CUTCAKE - Eat all the brownies !

BrownieDude was given the job of cutting cake at a party for serving the guests. But BrownieDude is both lazy and hungry, so he wants to cut the cake into maximum number of pieces with minimum number of cuts and go off to eating brownies.

The host of the party says that BrownieDude can cut the cake into unequal pieces but cannot cut in more than one plane. (Only vertical cuts are allowed.) Given the number of guests, find the number of cuts sufficient to generate the cake pieces.

Input

First line contains 't', the number of test cases. 't' lines follow. (1 ≤ t ≤ 1000)

Each line denotes the number of guests. (1 ≤ n ≤ 1011)

Output

One number denoting the number of cuts.

Note: It is guaranteed that an integer solution will always exist.

Example

Input:
2
1
2

Output:
0
1

Explanation for test cases: If there is only one guest, there is no need to cut the cake. If there are 2 guests, the cake can be cut into 2 pieces in 1 cut.


Added by:Pandian
Date:2013-12-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2015-11-26 15:35:49 (Tjandra Satria Gunawan)(曾毅昆)
"Only vertical cuts are allowed" this is misleading statement. got AC after assuming "only straight line cuts are allowed", straight line cut not necessarily vertical, it can be horizontal, diagonal, etc too..

Edit: maybe I don't know what exactly the meaning of the word "vertical" here.. My english is not good.

Last edit: 2015-11-26 15:45:42
2015-09-25 17:26:35 Abishek
use long long ...long is giving wrong answer .
2015-08-30 22:30:59
Ac in one go..no precision loss..:D
2015-08-25 14:54:55 KD
easy one
2015-08-18 19:54:19 shantanu tripathi
nice:D
2015-06-14 15:00:35 i_am_looser
It's easy, you just need to take paper,pen and draw some lines on circular cake.
Cake can be of any shape.... ; )
2015-03-05 17:27:41 Sayak Haldar
To all the coders who will try this problem, dont get confused be reading the comments. The cake need not to be circular. The cake could be of any shape...for example, even if you choose rectangular shapes cake, the maximum no. of pieces will be 7 after 3 cuts....just focus on the words ' maximum' and 'unequal pieces'...and of course 'vertical cuts'

Last edit: 2015-07-02 14:25:56
2014-12-23 05:11:30 Abhishek
Does the number of peices be EXACTLY equal to the number of guests or any less will suffice?
2014-09-16 14:20:44 Sandip Jana
Learned A lot... Good Question...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.