궁극의 장치

토미스 유령 씨는 궁극의 장치를 만들려고 한다. 이 장치를 만들려면 여러 종류의 회로가 필요하다.

상점에는 $n$가지 종류의 회로가 있고, $i$번째 종류의 회로는 소손 주기 $t_i$초를 가진다. 소손 주기가 $t_i$인 회로를 장치에 사용하면, 그 회로는 $t_i$초의 배수가 되는 모든 시각(즉 $t_i, 2t_i, 3t_i, \dots$초)마다 소손 상태에 들어간다.

어떤 시각에 장치 안의 회로 중 하나라도 소손 상태가 아니라면, 모든 회로는 그 순간을 무사히 넘긴다. 그러나 그 시각에 장치 안의 모든 회로가 동시에 소손 상태라면, 회로들은 함께 타 버리고 장치는 고장 난다. 다시 말해 어떤 회로 집합을 사용할 때 장치가 고장 나는 시각은 선택한 소손 주기들의 최소공배수(LCM)이다.

예를 들어 소손 주기가 각각 $3$초, $5$초인 두 회로를 함께 사용한다고 하자. $3$초에는 1번 회로만 소손 상태이므로 둘 다 살아남고, $5$초에는 2번 회로만 소손 상태이므로 역시 둘 다 살아남으며, $6$초에는 다시 1번 회로만 소손 상태이다. 결국 $15$초에 두 회로가 동시에 소손 상태가 되어 함께 타 버린다. 소손 주기가 $3, 4, 5$초인 세 회로를 모두 함께 쓰면 $60$초에 타 버리고, 앞의 두 회로($3, 4$)만 쓰면 $12$초에 타 버린다.

토미스 씨는 회로들을 하나씩 차례로 살펴본다. 각 회로 앞에서 공정한 동전을 던져, 앞면이 나오면 그 회로를 선택하고 뒷면이 나오면 버린다. $n$번째 회로까지 모두 살펴보고 나면 선택된 회로들의 집합이 정해지고, 그 집합으로 장치를 만든다. 이때 장치의 기대 수명을 구하라. 아무 회로도 선택되지 않았다면 장치의 수명은 $0$이다.

입력의 첫 줄에는 테스트 케이스의 수 $T$ ($T \le 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 회로의 개수 $n$ ($1 \le n \le 100$)이 주어진다. 다음 줄에는 $n$개의 정수가 공백으로 구분되어 주어지며, $i$번째 정수는 $i$번째 회로의 소손 주기 $t_i$ ($1 \le t_i \le 500$)이다. 한 테스트 케이스 안의 소손 주기들은 모두 서로 다르다.

각 테스트 케이스마다 먼저 케이스 번호를 출력하고, 이어서 $(r \cdot 2^n) \bmod 10007$을 출력한다. 여기서 $r$은 장치의 기대 수명이다. 만약 $r \cdot 2^n$이 정수가 아니라면 따옴표 없이 not integer를 출력한다.

출력 형식은 Case x: y이며, $x$는 케이스 번호(1부터 시작), $y$는 위에서 계산한 값이다.