TQ有点二

题目描述

TQ最近有点忙，所以导致他现在有点二。现在二二的TQ想要你帮忙帮他判断一个数是不是2的幂，如果是，请输出222。不是话，请输出这个数在二进制存储编码时有多少个1。

输入

多组数据输入

第一行输入组数T$(0<T\le1000000)$。

接下来T行，每行输入一个整数n$(0<n<2^{63})$

输出

对于每组数据，输出一行题目对应的要求。

输入样例

3
2
3
5

输出样例

222
2
2

样例解释

2是2的幂，所以输出222，3不是，3的二进制存储为11，所以输出2，5的二进制存储为101，所以输出2。