너무 시시했다

면접 대비

시간 제한2초메모리 제한1024 MB

요약

질의마다 x와 y를 받아 a + b = x이고 a XOR b = y인 음이 아닌 정수 순서쌍 (a, b)의 개수를 구합니다.

문제

영욱이는 민성이에게 다음과 같은 문제를 냈다.

음이 아닌 두 정수 $x$ 와 $y$ 에 대해서 $a + b = x$ 이고 $a \oplus b = y$ 인 음이 아닌 두 정수의 순서쌍 $(a, b)$ 는 모두 몇 개일까? (단, $\oplus$ 는 bitwise xor이다.)

민성이는 이 문제가 너무 시시했다. 그러니 여러분이 대신 풀어 주자. 한 문제만 푸는 건 너무 시시하니까, $q$ 문제를 동시에 풀어서 그나마 흥을 돋워 보자.

첫 번째 줄에 질문의 수 $q$ 가 주어진다.

두 번째 줄부터 $(q + 1)$ 번째 줄까지 각 줄에 질문마다 $x$ 와 $y$ 가 공백으로 구분되어 차례로 주어진다.

각 질문에 대해 조건을 만족하는 $(a, b)$ 쌍의 개수를 구하여 한 줄에 하나씩 차례로 출력한다.