Ultimate Device#4095
Mr. Tomisu Ghost is planning to build the ultimate device. He shared the idea with me but asked me to keep it secret. Therefore, I will not describe the functionalities of this great device or the mechanisms to build it.
However, Mr. Tomisu has planned to buy some circuits for this device from a local store, so he went to the store. He found that there were types of circuits, and each of the -th circuits has a burning cycle of t_i seconds. The burning cycle of a circuit means that if it’s used in the device, it will enter its burning state every t_i seconds. If there is any other circuit in the device that is not in its burning state at that time, then every circuit will survive and no damage will happen. But if every circuit is in its burning state at that time, all will burn out together, and the device will malfunction.
For example, consider two circuits with burning cycles of and seconds respectively, and let both of them be used in the device together. At the -rd second, circuit will be in its burning state, but since the other one is not in its burning state, it will survive. At the -th second, circuit will be in its burning state while circuit will not, thus circuit will also survive. At the -th second, circuit will be in its burning state again, but it will survive for the same reason. Thus, at the -th second, both circuits will be in their burning state and will burn out. If there are three circuits with burning cycles of , , and seconds respectively, and all of them are used together, they will burn out at the -th second. But if only the first two circuits are used, they will burn out at the -th second.
Now, Mr. Tomisu wants to go through all the circuits one by one. In front of every circuit, he will flip a coin (assume that it's a fair coin). If it's a head, he will select the circuit; otherwise, he will reject it. After visiting the -th circuit, he will have some selected circuits for his device. You have to help him by calculating the expected lifetime of his device. If no circuit is selected, then the lifetime of the machine is .
Input starts with an integer (T \le 100), denoting the number of test cases.
Each case starts with an integer (1 \le n \le 100), where denotes the number of circuits. The next line contains space-separated integers, where the -th integer denotes the burning cycle of the -th circuit, t_i (1 \le t_i \le 500). You may assume that all the burning cycles for a test case will be distinct.
For each case, print the case number first. Then print (r \cdot 2^n) \bmod 10007, where is the expected lifetime of the device. If (r \cdot 2^n) is not an integer, print not integer.
Example
2
2
3 5
3
3 4 5Case 1: 19
Case 2: 83Example 1
No additional notes.