题目描述

2026 丙午马年，一位少年骑手报名参加马拉松骑行挑战赛。赛道上的打卡点以正整数编号（\(1, 2, 3, \ldots\)），若两个打卡点的编号 \(i, j\) 满足 \(\text{popcount}(i \oplus j) = 1\)，则它们之间有一条长度为 \(1\) 的赛道。

少年从 \(1\) 号打卡点出发，目标是到达 \(n\) 号打卡点。请你帮他算出最短路的长度。

其中 \(\text{popcount}(x)\) 表示 \(x\) 在二进制下 \(1\) 的个数， \(\oplus\) 表示按位异或。

输入格式

输入 \(T\ (1 \le T \le 5 \cdot 10^4)\)，表示数据组数。

接下来 \(T\) 行，每行一个正整数 \(n\ (1 \le n \le 10^9)\)。

输出格式

对于每组数据，输出一行一个整数，表示最短路的长度。

样例输入

3
4
1
7

样例输出

2
0
2