XOR 집합 확장

숫자 집합 $S_0$가 주어진다. 아래 알고리즘은 새로운 값이 더 나오지 않을 때까지 집합을 넓히면서, 몇 번 넓혔는지 센다.

counter = 0
S = S0
loop:
    S' = { a xor b : a in S, b in S0, a != b }
    if every value of S' is already in S:
        print counter and stop
    S = S union S'
    counter = counter + 1
    goto loop

한 번의 반복에서는 이미 $S$에 있는 값 하나와 처음 주어진 $S_0$의 값 하나를 XOR 한 결과를 모두 모아 $S'$을 만든다. 같은 값끼리는 짝으로 쓰지 않으므로 0은 $S$에 들어가지 않는다. 새로운 값이 하나도 나오지 않는 반복에 이르면 그때의 counter를 출력하고 끝난다.

$S_0$ = {1, 2, 4}이면 알고리즘은 이렇게 돌아간다.

• 시작 상태: counter = 0, S = {1, 2, 4}
• 첫 번째 반복: S' = {3, 5, 6}, S = {1, 2, 3, 4, 5, 6}, counter = 1
• 두 번째 반복: S' = {1, 2, 3, 4, 5, 6, 7}, S = {1, 2, 3, 4, 5, 6, 7}, counter = 2
• 세 번째 반복: S' = {1, 2, 3, 4, 5, 6, 7}에 새로운 값이 없으므로 2를 출력하고 끝난다.

원소가 하나뿐인 집합은 XOR 할 짝이 없어 $S'$이 공집합이 되고, 답은 0이다.

$S_0$가 주어졌을 때 알고리즘이 출력하는 counter의 값을 구하는 프로그램을 작성하여라.

첫 줄에 테스트 케이스의 수를 나타내는 양의 정수 $T$가 주어진다. $T$는 100,000 이하다.

각 테스트 케이스는 두 줄이다. 첫 줄에는 초기 집합 $S_0$의 크기 $N$이 주어지고, $N$은 1 이상 50 이하다. 둘째 줄에는 $S_0$의 원소 $N$개가 공백으로 구분되어 주어진다. 모든 원소는 1 이상 500,000 이하의 정수이고 서로 다르다.

각 테스트 케이스마다 한 줄에 Case #x: R 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $R$은 알고리즘이 출력하는 counter의 값이다.