Description

For given $N$, find the smallest $pp$,no smaller than $N$ for which there exists an positive integer $hh$ for which

$2hh(hh + 1) = pp(pp + 1)$

Format

Input

This problem contains multiple test cases. The first line of a multiple input is an integer $T (1 <T < 1000)$

followed by T input lines. Each line contains an integer $N (1 < N < 8*10^{18})$

Output

For each given $N$, output the smallest $pp$, If available $pp$ does not exist, output $-1$

Samples

1
1

Case #1: 3