In this problem you are given a pizza. You have to find the maximum number of slices after cutting the pizza exactly N times.

Note that it is not necessary to make each slice equal.

For example if N = 1 then we can make maximum 2 slices. Figure 1 show this.

If N = 2 then we can make maximum 4 slices. Figure 2 show this.

Input

Input starts with an integer T (1 ≤ 10⁶), denoting the number of test cases.

Each case contains an integer N (1 ≤ N ≤ 10⁹) denoting the number of times you can cut the pizza.

Output

For each case of input, output only one integer the maximum number of slices.

Example

Input:
2
1
2
Output:
2
4