Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Where Do Lovers Go?

By YouKnowWho · Limits 1s, 512 MB · Custom Checker

Cherry isn't feeling well right now as she found a problem that she couldn't solve. So she started to listen to Where Do Lovers Go? and you, to make her happy, have to solve the problem for her.

You are given an integer nn. You have to find an integer kk (1k10181 \le k \le 10^{18}) such that the following conditions are satisfied:

  • kk is a multiple of nn
  • n&k=0n \, \& \, k = 0. Here, &\& is the bitwise AND operator.

Input

The first line of the input contains a single integer tt (1t1051 \le t \le 10^5) denoting the number of test cases. The description of tt test cases follows.

The first and only line of each test case contains an integer nn (1n1081 \le n \le 10^8).

Output

For each test case, print a single line containing an integer kk (1k10181 \le k \le 10^{18}) satisfying the aforementioned conditions.

If there are multiple solutions, output any. It can be shown that an answer always exists under the given constraints.

Sample

InputOutput
3
5
34
69
10
340
4002

    Discussion

    Statistics


    64% Solution Ratio

    Ashiqur.141492Earliest, 9M ago

    fahimcp495Fastest, 0.0s

    ABIR_RULightest, 1.6 MB

    steinumShortest, 58B

    Submit

    Login to submit

    Editorial

    For nnn, the answer is n×230n \times 2^{30}n×230.

    Toph uses cookies. By continuing you agree to our Cookie Policy.