사탕 나누기 게임

알고리즘 유치원 선생님인 영희는 간식 시간이 되어 아이들에게 사탕을 나누어 주었다. 하지만 욕심 많은 아이들이 순서를 무시하고 사탕을 마구 집어 가는 바람에, 사탕을 많이 가진 아이가 있는가 하면 거의 갖지 못해 우는 아이도 생겼다.

그래서 영희는 다음과 같은 놀이를 제안했다. 모든 아이가 원을 이루어 둘러앉는다. 한 순환은 다음 두 단계가 차례대로 일어난다.

1. 모든 아이가 동시에 자기가 가진 사탕의 절반을 오른쪽에 앉은 아이에게 준다. 즉 각 아이는 자기 사탕의 절반을 남기고, 왼쪽에 앉은 아이에게서 그 아이 사탕의 절반을 받는다.
2. 이 결과 사탕을 홀수 개 갖게 된 아이가 있으면, 선생님이 그 아이에게 한 개를 보충해 짝수로 만들어 준다.

이 과정을 몇 번 반복하면 모든 아이가 같은 개수의 사탕을 갖게 되어 놀이가 끝난다.

‘오른쪽에 절반을 주는 단계’와 ‘선생님이 보충하는 단계’를 묶어 한 순환이라고 할 때, 모든 아이가 같은 개수의 사탕을 갖기까지 몇 순환이 필요한지 구하여라.

단, 처음부터 홀수 개의 사탕을 가진 아이가 있으면 선생님이 먼저 짝수로 보충해 주며, 이 최초 보충은 순환 수에 포함되지 않는다. 선생님은 충분히 많은 사탕을 가지고 있다고 가정한다.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 아이의 수 $N$ ($1 \le N \le 10$)이 주어지고, 둘째 줄에는 각 아이가 처음에 가진 사탕의 개수 $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 30$)이 공백으로 구분되어 주어진다. 자리 배치는 $C_1$의 오른쪽에 $C_2$, $C_2$의 오른쪽에 $C_3$, $\dots$ 와 같이 이어지며, $C_N$의 오른쪽에는 다시 $C_1$이 앉는다.

각 테스트 케이스마다, 모든 아이가 같은 개수의 사탕을 가질 때까지 걸리는 순환의 수를 한 줄에 하나씩 출력한다.