A-数字游戏_牛客小白月赛40

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$dd$ 在玩数字游戏，首先他拿到一个 $x$
当 $x$ 不为零时进行如下操作
如果二进制 $x$ 中有奇数个 $1$ ，则 $x$ 二进制形式下最低位取反（即 $0$ 变成 $1$ , $1$ 变成 $0$ ）
如果二进制 $x$ 中有偶数个 $1$ ，则 $x$ 二进制形式下非前导零最高位取反
询问对于一个 $x$ ，操作几次后变为零

输入描述:

第一行一个正整数(1≤T≤1000000)，表示询问组数
接下来T行，每行一个数x（0≤x≤1000000000）表示询问的数字
由于本题数据量比较大，请选择较快的读入方式

输出描述:

输出T行，每行是对应的答案

示例1

输入

复制

输出

复制

0
1
2