CUTCAKE - Eat all the brownies !

no tags 

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.


hide comments
Kevin Sebastian: 2013-12-23 10:58:25

@author what exactly does 'vertical cuts' mean?

Last edit: 2013-12-23 13:34:11
Ashwini Singh: 2013-12-22 21:07:12

@pandian: i think the problem statement is incomplete...check soln id 10718194

Edit : AC...didnt find d 'optimum' method.

Last edit: 2013-12-22 21:18:12
Prashant Kiran: 2013-12-22 20:38:32

can you please check my logic
id=10718094

sprinter: 2013-12-22 14:53:37

plzz provide some test cases...

Bhavik: 2013-12-22 14:03:10

@pandian: thank you:)
Got it Ac

ABHISHEK: 2013-12-22 13:22:30

getting WA can you please check 10715279

Pandian: 2013-12-22 13:16:03

@gru and @ bhavik : Your logic is not right.

Bhavik: 2013-12-22 12:15:35

@pandian: can u kindly chk id:10715046
tell me if i am thinking right??

Last edit: 2013-12-22 12:33:10
Pandian: 2013-12-22 06:55:30

@gru : Your logic is wrong !

anurag garg: 2013-12-22 05:49:39

AC good question...
I like cake...


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