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
2013-12-26 12:12:10 [Lakshman]
@Pandian can you please check MY Last Lisp submission getting WA with same logic

Thanks.
2013-12-26 09:46:36 [Lakshman]
@Pandian nice proble.
2013-12-25 20:32:11 Kanish
@PANDIAN pls check my submission id 10737761
2013-12-25 06:51:14 Pandian
Vertical cut means u cannot cut the cake with a cut horizontal to the surface of the floor. You can only use a cut which is perpendicular to the surface of the floor.
2013-12-24 20:35:06 Kevin Sebastian
@pls check my submission id 10731587..it is the optimal method

Last edit: 2013-12-25 07:34:13
2013-12-24 11:22:45 Yashvir Singh
@Pandian what's exactly "vertical cuts"?
2013-12-24 08:16:49 shiv prasad chabarval
@pandian why i m getting WA i hv tried this wid all the 3 possible methods but still WA
nyone plz help <snip>

Last edit: 2023-02-05 22:24:42
2013-12-23 17:46:43 Manu Narsaria
Some More test cases pls...
2013-12-23 11:03:24 Kevin Sebastian
@pandian can u chk id 10721436 and see if I am thinking right?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.