马上就要到羊年了，羊村一片欢腾，懒羊羊则懒洋洋地躺在草坪上吃新年的巧克力棒。
他手上的巧克力棒是个由 $n$ 个巧克力单元格组成的长度为 $n$ 的长条，现在懒羊羊想把巧克力棒掰开成一个个小单元格。
初始时懒羊羊会把这根巧克力棒丢在草坪上，然后每次懒羊羊会从草坪上拿起一根长度大于 $1$ 的巧克力棒，然后从某两个相邻的单元格的间隙处掰开变成两根巧克力棒，然后把这两根巧克力棒丢在草坪上。
懒羊羊初始愉悦值为 $0$，每次掰开巧克力棒后如果这两根巧克力棒长度相等，那么懒羊羊将提升 $1$ 点愉悦值。
当然，草坪上全是长度为 $1$ 的巧克力棒时懒羊羊就会停止操作。现在懒羊羊想知道，他能获得的愉悦值最多是多少？
第一行包含一个正整数 $T$ ($T \leq 20$)。
接下来 $T$ 行，每行一个正整数 $n$ ($n \leq 10^9$) 表示巧克力棒的长度，你需要对每个给出的 $n$ 计算最多能获得的愉悦值。
输出 $T$ 行，每行一个整数，表示懒羊羊最多能获得的愉悦值。
一眼就能看到一个 DP 的做法。设 $f_i$ 表示有一根长度为 $i$ 的巧克力棒，懒羊羊所能获得最大愉悦值，则有边界 $f_1 = 0$ 和转移 $$ f_n = \max_{0 < i < n} \left( f_i + f_{n-i} + [n = 2i] \right) $$
简单打个表可以发现，这里的 $f_n = n - \popc(n)$ ($\popc(n)$ 为种群计数函数，定义为 $n$ 的二进制展开式中 $\texttt 1$ 的个数)，这是为什么呢？下面来归纳证明一下。
当 $k = 1$ 时显然正确。设当 $k < n$ 时正确，那么考虑 $f_n$，根据转移方程，有
$$ f_n = \max_{0 < i < n} \left( f_i + f_{n-i} + [n = 2i] \right) = \max_{0 < i < n} \left( i - \popc(i) + (n - i) - \popc(n - i) + [n = 2i] \right) = n - \min_{0 < i < n} \left( \popc(i) + \popc(n - i) - [n = 2i] \right) $$
根据加法的规则，有下列不等式成立 $\popc(i) + \popc(j) \geq \popc(i+j)$ 且当且仅当 $i+j$ 在二进制中加法不进位 (即 $i \mathbin{\&} j = 0$，其中 $\&$ 为按位与运算)。此时分两种情况讨论：
若 $n$ 是 $2$ 的幂，由于 $0 < i < n$，因此 $i$ 与 $n - i$ 相加必有进位，故此时不等号无法成立，因此有 $\popc(i) + \popc(n - i) \geq \popc(n) + 1$，那么 $\popc(i) + \popc(n - i) - [n = 2i] \geq \left( \popc(n) + 1 \right) - 1 = \popc(n)$，且当 $i = \dfrac n2$ 时等号成立。
若 $n$ 不是 $2$ 的幂，此时由于 $\popc(n) \geq 2$，故必存在 $i$ 使得 $\popc(i) + \popc(n - i) = \popc(n)$ (事实上，取 $i$ 为小于 $n$ 的最大的 $2$ 的幂即可)，此时原式可以达到 $\popc(n)$。
但是该式有没有可能小于 $\popc(n)$ 呢？如果存在，那么只可能是 $i = \dfrac n2$，但此时会有 $i = n - i$，于是两个相同的数相加 (在二进制下) 必定会有进位 (或者说 $i \mathbin{\&} (n-i) \neq 0$)，故不会小于 $\popc(n)$。
综上所述，对于任意 $n \geq 2$ 都有 $\min\limits_{0 < i < n} \left( \popc(i) + \popc(n - i) - [n = 2i] \right)$，因此当 $k = n$ 时也正确。由归纳法知，我们刚猜测的结论是正确的。
#include <bits/stdc++.h>
#define popc __builtin_popcount
using namespace std;
int n;
int main(){
int T;
for(scanf("%d", &T); T; --T){
scanf("%d", &n);
printf("%d\n", n - popc(n));
}
return 0;
}
无