← 返回题目列表

Codeforces · 1343/A

A. 糖果

中文机器翻译题面 查看原题

最近 Vova 发现了 $$$n$$$ 糖果包装纸。他记得第一天买了 $$$x$$$ 糖果,第二天买了 $$$2x$$$ 糖果,第三天买了 $$$4x$$$ 糖果,第 $$$k$$$ 买了 $$$\dots$$$、$$$2^{k-1} x$$$ 糖果。但有一个问题:Vova 既不记得 $$$x$$$ 也不记得 $$$k$$$,但他确信 $$$x$$$ 和 $$$k$$$ 是正整数,并且 $$$k > 1$$$。

如果你告诉他任何正整数 $$$x$$$,Vova 就会满意,因此有一个整数 $$$k>1$$$ 满足 $$$x + 2x + 4x + \dots + 2^{k-1} x = n$$$。保证至少存在一个解。请注意 $$$k > 1$$$。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的唯一一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10^9$$$) — Vova 找到的糖果包装纸的数量。保证存在某个正整数$$$x$$$ 和整数$$$k>1$$$ 使得$$$x + 2x + 4x + \dots + 2^{k-1} x = n$$$。

输出

打印一个整数 - $$$x$$$ 的任何正整数值,因此存在一个整数 $$$k>1$$$ 且 $$$x + 2x + 4x + \dots + 2^{k-1} x = n$$$。

示例

输入 #1

7
3
6
7
21
28
999999999
999999984

输出 #1

1
2
1
7
4
333333333
333333328

注意

在示例的第一个测试用例中,可能的答案之一是 $$$x=1, k=2$$$。那么 $$$1 \cdot 1 + 2 \cdot 1$$$ 等于 $$$n=3$$$。

在示例的第二个测试用例中,可能的答案之一是 $$$x=2, k=2$$$。那么 $$$1 \cdot 2 + 2 \cdot 2$$$ 等于 $$$n=6$$$。

在示例的第三个测试用例中,可能的答案之一是 $$$x=1, k=3$$$。那么 $$$1 \cdot 1 + 2 \cdot 1 + 4 \cdot 1$$$ 等于 $$$n=7$$$。

在示例的第四个测试用例中,可能的答案之一是 $$$x=7, k=2$$$。那么 $$$1 \cdot 7 + 2 \cdot 7$$$ 等于 $$$n=21$$$。

在示例的第五个测试用例中,可能的答案之一是 $$$x=4,k=3$$$。那么 $$$1 \cdot 4 + 2 \cdot 4 + 4 \cdot 4$$$ 等于 $$$n=28$$$。