题目描述

给定一个正整数 $a$，输出一个正整数 $n$，使得 $a\times\operatorname{popcount}(n)=n$，其中 $\operatorname{popcount}$ 表示二进制表示中 $1$ 的个数，如果不存在，输出 $-1$，如果答案不唯一，可以输出任意一个。

你需要解决 $T$ 个这样的问题。

输入格式

第一行输入一个正整数 $T$，表示问题的个数。

第 $i+1\ (1\le i\le T)$ 行输入一个正整数 $a$，表示第 $i$ 个问题。

输出格式

输出 $T$ 行，第 $i\ (1\le i\le T)$ 行输出一个整数表示第 $i$ 个问题的答案。

3
5
27
26

10
81
-1

提示

样例解释

对于第 $1$ 个问题，$5\times\operatorname{popcount}(10)=5\times 2=10$。

对于第 $2$ 个问题，$27\times\operatorname{popcount}(81)=27\times 3=81$，另外 $108$ 也是一个答案。

对于第 $3$ 个问题，可以证明不存在正整数 $n$ 使得 $26\times\operatorname{popcount}(n)=n$。

数据范围

对于所有测试数据，保证：

• $1\le T\le 10^5$；
• $1\le a\le 10^{16}$。

::cute-table{tuack} |测试点编号|$a\le$|$T\le$|特殊性质| |:-:|:-:|:-:|:-:| |$1$|$10$|$10$|无| |$2$|$4000$|$1000$|保证有解| |$3,4$|^|^|无| |$5$|$10^{16}$|$54$|$a$ 是 $2$ 的幂| |$6\sim 10$|^|$10^5$|无|