노 솔브 방지 문제야!!

여러분은 $Q$개의 쿼리를 수행해야 합니다. 수행해야 하는 쿼리는 다음과 같습니다.

어떤 수 $a$를 2의 거듭제곱 꼴로 나타낼 수 있는가?

첫 줄에 $Q$가 주어집니다. ($1 \le Q \le 10^6$)

두 번째 줄부터 $Q+1$번째 줄까지 $a$가 주어집니다. $a$는 $1$ 이상 $2^{31}-1$ 이하 자연수입니다.

각 쿼리마다, 답이 Yes이면 1을, 그렇지 않으면 0을 출력합니다.

어떤 수 $a$가 2의 거듭제곱 꼴로 나타내어진다고 해 봅시다. 그렇다면 $a = 2^n$ (단 $n \ge 0$인 정수)을 만족합니다. 보통은 각 비트를 검사하면서 켜져 있는 비트의 개수를 세는 것도 좋은 방법입니다. 이때에는 많아야 32번 정도 연산을 수행하고, 전체 쿼리가 $Q$개라면 총 시간 복잡도는 $O(32Q)$가 됩니다.

그런데 더 좋은 방법이 없을까요? $x$ ($x \ge 0$)를 2진법으로 표현해 보고, $x$가 홀수인 경우와 짝수인 경우로 나눠 봅시다.

...01

이때 $-x$는 어떻게 표현될까요?

...11

따라서 $x\&(-x)$를 하면 1이 나옵니다. $x$가 짝수라면 어떨까요?

...10...0

으로 표현될 겁니다. 이때 $-x$는 어떻게 표현될까요? 일단 비트를 반전시켜 봅시다.

...01...1

이 되고, 여기에 1을 더한 것이 2의 보수 표현법입니다. 따라서 $-x$는

...10...0

으로 표현됩니다. 따라서 $x\&(-x)$는 $x$에서 1이 있는 최하위 비트와 관련이 있음을 알 수 있습니다. 예를 하나 들어봅시다. $x=6$인 경우 $x\&(-x)$의 값은 어떻게 나올까요?

$6 = ...0110$

$-6 = ...1010$

이므로 $6\&(-6) = 2$가 나옵니다.

그러면 $a$가 $2^i$ 꼴로 나타내어진다면 어떤 성질이 있는지 관찰해 봅시다.

$a = 0...010...0$

$-a = 1...110...0$

따라서 $(a\&(-a)) == a$라면 2의 거듭제곱이고, 그렇지 않으면 2의 거듭제곱이 아닙니다.