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" без кавычек.