Ultimate Device
Містер Томісу Гост планує створити найкращий пристрій. Він поділився зі мною цією ідеєю, але попросив зберегти її в таємниці. Тому я не буду розповідати про функціональні можливості цього чудового пристрою і також не хочу описувати механізми його створення.
Однак, пан Томісу планував купити деякі схеми для цього пристрою в місцевому магазині, і для цього він пішов до магазину. Він виявив, що є n типів схем, і кожна з i-тих схем має цикл загоряння t_i секунд. Цикл загоряння схеми означає, що якщо вона використовується в пристрої, вона буде входити в стан загоряння кожні t_i секунд. Якщо в пристрої є інша схема, яка не знаходиться в стані загоряння, то всі схеми виживуть і ніякої шкоди не буде. Але якщо всі схеми в цей час знаходяться в стані загоряння, всі вони згорять разом, і пристрій вийде з ладу.
Наприклад, розглянемо дві схеми з циклом загоряння 3 і 5 секунд відповідно, і нехай обидві вони використовуються в пристрої разом. На 3-ій секунді схема 1 буде в стані загоряння, але оскільки інша не в стані загоряння, вона виживе. На 5-ій секунді схема 2 буде в стані загоряння, тоді як схема 1 не буде в стані загоряння, таким чином схема 2 також виживе. На 6-ій секунді схема 1 знову буде в стані загоряння, але виживе з тієї ж причини. Таким чином, на 15-ій секунді обидві схеми будуть в стані загоряння і згорять. Якщо є три схеми з циклом загоряння 3, 4 і 5 секунд відповідно і всі вони використовуються разом, вони згорять на 60-ій секунді. Але якщо використовуються лише перші дві схеми, то вони згорять на 12-ій секунді.
Тепер пан Томісу хоче пройти всі схеми одну за одною. Перед кожною схемою він підкине монету (припустимо, що це чесна монета). Якщо випаде орел, він вибере схему, інакше відхилить її. Після відвідування n-тої схеми у нього буде кілька вибраних схем для свого пристрою. Ви повинні допомогти йому, обчисливши очікуваний термін служби його пристрою. Якщо жодна схема не вибрана, то термін служби машини дорівнює 0.
Вхідні дані
Вхід починається з цілого числа T (≤ 100), що позначає кількість тестових випадків.
Кожен випадок починається з цілого числа n (1 ≤ n ≤ 100), де n позначає кількість схем. Наступний рядок містить n розділених пробілами цілих чисел, де i-те число позначає цикл загоряння i-тої схеми, t_i (1 ≤ t_i ≤ 500). Ви можете припустити, що всі цикли загоряння для тестового випадку будуть різними.
Вихідні дані
Для кожного випадку спочатку надрукуйте номер випадку. Потім надрукуйте (r·2^n) modulo 10007, де r — це очікуваний термін служби пристрою. Якщо (r·2^n) не є цілим числом, надрукуйте "not integer" без лапок.