번부터 번까지 번호가 붙은 개의 정점이 있다. 이상의 정수 를 정한 뒤, 서로 다른 두 정점 , 의 모든 쌍에 대해 이면 두 정점을 무방향 간선으로 연결하고, 그렇지 않으면 연결하지 않는다.
는 비트 단위 XOR 연산이다. 두 수를 이진수로 나타냈을 때 같은 자릿수의 비트가 서로 다르면 , 같으면 인 비트를 갖는 수를 계산한다. 예를 들어, 이다.
그래프의 연결 요소는 간선을 따라 서로 오갈 수 있는 정점들을 최대한 모은 집합이다. 어떤 간선과도 연결되지 않은 정점도 하나의 연결 요소를 이룬다.
그래프의 연결 요소 개수가 이하가 되도록 하는 가장 작은 이상의 정수 를 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 그래프의 연결 요소 개수가 이하가 되도록 하는 가장 작은 이상의 정수 를 한 줄에 출력한다. 테스트 케이스가 입력된 순서대로 출력한다.
이면 간선이 없으므로 연결 요소는 개이다. 처음 세 테스트 케이스에서는 이므로 정답이 이다. 나머지 테스트 케이스에서는 모두 이다.
첫째 줄에 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
한 줄에 두 정수 과 가 공백으로 구분되어 주어진다.
