BICAKE - Birthday cake

Wersja polska English version

John even on birthday solves mathematician prolems. As a good host he wants to cut the cake for guests personally so that everyone gets a one piece. He had a hard day (he had to write a long essay), that is why he wants to do as few cuts as possible to keep power for partying. The size of each piece of that cake is irrelevant because everyone has a different appetite and no one will be neglected. Write a program which will help John. The program must print the minumum number of cuts he must do.

Input

The number of tests is unknown (John is very inquisitive and he likes to consider various options). Every test consists of a one number 0 < n < 8*1012 + 3*106 that is a number of guests.

Output

For a given n print the number of straight cuts that divide the cake into n pieces.

Example

Input:
2
7

Output:
1
3


Added by:Adam Bąk
Date:2011-02-16
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.