Ultimate Device

Mr. Tomisu Ghost wants to build the ultimate device. Building it requires several kinds of circuits.

A store sells $n$ kinds of circuits. The $i$-th kind has a burning cycle of $t_i$ seconds: if a circuit with burning cycle $t_i$ is placed in the device, it enters its burning state at every multiple of $t_i$ seconds (that is, at seconds $t_i, 2t_i, 3t_i, \dots$).

At any given second, if at least one circuit in the device is not in its burning state, then every circuit survives that moment. But if all circuits in the device are in their burning state at the same second, they all burn out together and the device fails. In other words, if a set of circuits is used, the device fails at the time equal to the least common multiple (LCM) of the chosen burning cycles.

For example, take two circuits with burning cycles $3$ and $5$ used together. At second $3$ only circuit 1 is burning, so both survive; at second $5$ only circuit 2 is burning, so both survive; at second $6$ only circuit 1 is burning again. Finally, at second $15$ both circuits are burning simultaneously and burn out. Three circuits with cycles $3, 4, 5$ used together burn out at second $60$, while using only the first two ($3, 4$) burns out at second $12$.

Mr. Tomisu inspects the circuits one by one. In front of each circuit he flips a fair coin: heads means he selects that circuit, tails means he rejects it. After inspecting all $n$ circuits, the selected circuits form his device. Compute the expected lifetime of the device. If no circuit is selected, the lifetime is $0$.

The first line contains an integer $T$ ($T \le 100$), the number of test cases.

Each test case begins with a line containing an integer $n$ ($1 \le n \le 100$), the number of circuits. The next line contains $n$ space-separated integers; the $i$-th integer is the burning cycle $t_i$ ($1 \le t_i \le 500$) of the $i$-th circuit. All burning cycles within a single test case are distinct.

For each test case, print the case number, followed by $(r \cdot 2^n) \bmod 10007$, where $r$ is the expected lifetime of the device. If $r \cdot 2^n$ is not an integer, print not integer without the quotes.

Use the format Case x: y, where $x$ is the case number (starting from 1) and $y$ is the computed value.