문제

다음 조건을 만족하는 길이가 인 수열 가 있다.

• ()
• 수열의 모든 원소를 XOR한 값은 0이다.

서로 다른 의 개수를 로 나눈 나머지를 구하여라.

입력

첫째 줄에 테스트 케이스의 개수 가 주어진다.

다음 개의 줄에 과 가 공백으로 구분되어 주어진다.

출력

각각의 테스트 케이스마다 문제의 정답을 한 줄에 하나씩 출력한다.

제약 조건

• 입력으로 주어지는 모든 수는 정수이다.