Mr Tomisu Ghost is planning to build The ultimate device. Though he shared the idea with me but requested me to keep this a secret. So, I am not going to expose the functionalities of this great device and also do not want to describe the mechanisms to build it.

Mr Tomisu went to buy some circuits for this device from a local store. He found that there were n types of circuits and each of the i^th circuits has the burning cycle of t_i seconds. Burning cycle of a circuit means that if it's used in the device, it will enter to its burning state at every t_i seconds. If there is any other circuit in the device that is not in its burning state, then every circuit will survive and no damage will happen. But if all circuits enter their burning state at that time, all will get burned and the device will be malfunctioned.

For example, consider two circuits used in the Device have the burning cycle of 3 and 5 seconds respectively. At 3^rd second, circuit 1 will be in its burning state, but since the other one is not in its burning state, it will survive. At 5^th second, circuit 2 will be in burning state while circuit 1 will not be in its burning state, thus circuit 2 will also survive. At 6^th second circuit 1 will be in its burning state again, but will survive for the same reason. Thus at 15^th second both circuits will be in their burning state and burn out. If there are three circuits in the device with the burning cycle of 3, 4 and 5 seconds respectively, they will burn out at 60^th second.

Now, with some superstition, 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 n^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 assumed to be 0.

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with an integer n (1 ≤ n ≤ 100), where n denotes the number of circuits. The next line contains n space separated integers, where the i^th integer denotes the burning cycle of the i^th circuit, t_i (1 ≤ t_i ≤ 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 * 2ⁿ) modulo 10007, where r is the expected lifetime of the device. If (r * 2ⁿ) is not an integer, print not integer.