Mr Tomisu Ghost is planning to build the ultimate device. He shared the idea with me but asked me to keep it secret. So, I am not going through the functionalities of this great device and I also do not want to describe the mechanisms to build it. However, Mr Tomisu has planned to buy some circuits for this device from a local store and for that he went to the store. He found that there were \textbf{n} types of circuits and each of the \textbf{i}^th circuits has the burning cycle of \textbf{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 \textbf{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 every circuit is at its burning state at that time, all will be burned out together and the device will be malfunctioned. For example, consider two circuits have the burning cycle of \textbf{3} and \textbf{5} seconds respectively and let both of them are used in the device together. At \textbf{3}^rd second, circuit \textbf{1} will be in its burning state, but since the other one is not in its burning state, it will survive. At \textbf{5}^th second, circuit \textbf{2} will be in burning state while circuit \textbf{1} will not be in its burning state, thus circuit \textbf{2} will also survive. At \textbf{6}^th second circuit \textbf{1} will be in its burning state again, but survive for the same reason. Thus at \textbf{15}^th second both circuits will be in their burning state and burn out. If there are three circuits with the burning cycle of \textbf{3}, \textbf{4} and \textbf{5} seconds respectively and all of them are used together, they will burn out at \textbf{60}^th second. But if the first two circuits are used only, then they will burn out at \textbf{12}^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 \textbf{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 \textbf{0}. \InputFile Input starts with an integer \textbf{T} (≤ \textbf{100}), denoting the number of test cases. Each case starts with an integer \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}), where \textbf{n} denotes the number of circuits. The next line contains \textbf{n}space separated integers, where the \textbf{i}^th integer denotes the burning cycle of the \textbf{i}^th circuit, \textbf{t_i} (\textbf{1} ≤ \textbf{t_i} ≤ \textbf{500}). You may assume that all the burning cycles for a test case will be distinct. \OutputFile For each case, print the case number first. Then print \textbf{(r·2^n) modulo 10007}, where \textbf{r} is the expected lifetime of the device. If \textbf{(r·2^n)} is not an integer print "\textbf{not integer}" without the quotes.