You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

2S/512M

题目描述

对于一个正整数 $x$，定义函数 $f(x)$ 为：

$$f(x) = \sum_{i = 0}^{\infty}\left\lfloor\frac{x}{2^i}\right\rfloor = \left\lfloor\frac{x}{2^0}\right\rfloor + \left\lfloor\frac{x}{2^1}\right\rfloor + \left\lfloor\frac{x}{2^2}\right\rfloor + \left\lfloor\frac{x}{2^3}\right\rfloor + \dots $$

其中，$\lfloor z\rfloor$ 表示对实数 $z$ 下取整，即不超过 $z$ 的最大整数。例如，$\left\lfloor\frac{5}{2}\right\rfloor = 2$。

你拥有一个初始正整数 $x$，可以执行任意次（包括 $0$ 次）以下操作：

• 将当前的 $x$ 更新为 $f(x)$，即令 $x:=f(x)$。

给定目标正整数 $y$，求初始时 $x$ 的最小值，使得经过若干次操作后，$x$ 的值恰好等于 $y$。

格式

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行包含一个正整数 $y$，表示该组测试数据的目标值。

输出格式

输出 $T$ 行。对于每组测试数据，输出一行一个整数，表示满足条件的初始值 $x$ 的最小值。

样例

样例输入 #1

3
3
5
19

样例输出 #1

2
5
2

样例解释 #1

对于第一组测试数据，$f(2) = 2 + 1 = 3$，因此可以选择初始值 $x = 2$。

对于第二组测试数据，初始值 $x = 5$ 时无需执行操作即可得到 $y = 5$。所有小于 $5$ 的正整数经过若干次操作后均无法得到 $5$，因此答案为 $5$。

对于第三组测试数据，从初始值 $x = 2$ 开始，可以依次得到

$$2 \to 3 \to 4 \to 7 \to 11 \to 19$$

因此答案为 $2$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$T\le$	$y\le$
$1$	$30$	$10$	$10^5$
$2$		$3000$
$3$	$40$		$10^{18}$

对于 $100\%$ 的数据，满足 $1 \le T \le 3000$，$1 \le y \le 10^{18}$。