XOR Set Expansion

A set of numbers $S_0$ is given. The algorithm below widens the set until no new value shows up, and counts how many times it widened the set.

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

One round collects every result of XOR-ing a value already in $S$ with a value of the original set $S_0$, and those results form $S'$. Equal values are never paired, so 0 stays out of $S$. Once a round yields no new value at all, the algorithm prints the current counter and stops.

For $S_0$ = {1, 2, 4} the algorithm runs like this.

• start: counter = 0, S = {1, 2, 4}
• round 1: S' = {3, 5, 6}, S = {1, 2, 3, 4, 5, 6}, counter = 1
• round 2: S' = {1, 2, 3, 4, 5, 6, 7}, S = {1, 2, 3, 4, 5, 6, 7}, counter = 2
• round 3: S' = {1, 2, 3, 4, 5, 6, 7} holds no new value, so the algorithm prints 2 and stops.

A set with a single element has no pair to XOR, so $S'$ is empty and the answer is 0.

Write a program that reads $S_0$ and computes the counter value the algorithm prints.

The first line has a positive integer $T$, the number of test cases. $T$ is at most 100,000.

Each test case takes two lines. The first line has $N$, the size of the initial set $S_0$, and $N$ is between 1 and 50. The second line has the $N$ elements of $S_0$, separated by spaces. Every element is an integer between 1 and 500,000, and all elements are different.

For each test case print one line in the form Case #x: R, where $x$ is the test case number starting at 1 and $R$ is the counter value the algorithm prints.