25367번 - 너무 시시했다

문제

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

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

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

입력

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

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

출력

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

제한

• 1 ≤ q ≤ 200 000
• 0 ≤ x ≤ 10¹⁸, 0 ≤ y ≤ 10¹⁸

힌트