Ultimate Cihaz#4095

Ultimate Cihaz

10 saniyə

64 meqabayt

Orta

Cənab Tomisu Ghost ən mükəmməl cihazı yaratmağı planlaşdırır. O, bu ideyanı mənimlə paylaşdı, lakin məndən bunu sirr saxlamağımı istədi. Buna görə də, bu böyük cihazın funksionallıqlarını izah etməyəcəyəm və onu yaratmaq üçün mexanizmləri təsvir etmək istəmirəm.

Lakin, cənab Tomisu bu cihaz üçün yerli mağazadan bəzi dövrələr almağı planlaşdırıb və bunun üçün mağazaya getdi. Orada $n$ növ dövrə olduğunu və hər bir $i$ -ci dövrənin yanma dövrünün $t_{i}$ t_i saniyə olduğunu öyrəndi. Dövrənin yanma dövrü o deməkdir ki, əgər o cihazda istifadə olunarsa, hər $t_{i}$ t_i saniyədə yanma vəziyyətinə keçəcək. Əgər cihazda yanma vəziyyətində olmayan başqa bir dövrə varsa, o zaman hər bir dövrə sağ qalacaq və heç bir zərər olmayacaq. Lakin, əgər həmin anda hər bir dövrə yanma vəziyyətindədirsə, hamısı birlikdə yanacaq və cihaz sıradan çıxacaq.

Məsələn, iki dövrənin yanma dövrü müvafiq olaraq $3$ və $5$ saniyədirsə və hər ikisi cihazda birlikdə istifadə olunursa, $3$ -cü saniyədə $1$ -ci dövrə yanma vəziyyətində olacaq, lakin digəri yanma vəziyyətində olmadığı üçün sağ qalacaq. $5$ -ci saniyədə $2$ -ci dövrə yanma vəziyyətində olacaq, lakin $1$ -ci dövrə yanma vəziyyətində olmayacaq, beləliklə $2$ -ci dövrə də sağ qalacaq. $6$ -cı saniyədə $1$ -ci dövrə yenidən yanma vəziyyətində olacaq, lakin eyni səbəbdən sağ qalacaq. Beləliklə, $15$ -ci saniyədə hər iki dövrə yanma vəziyyətində olacaq və yanacaq. Əgər yanma dövrü müvafiq olaraq $3$ , $4$ və $5$ saniyə olan üç dövrə varsa və hamısı birlikdə istifadə olunarsa, onlar $60$ -cı saniyədə yanacaq. Lakin yalnız ilk iki dövrə istifadə olunarsa, onlar $12$ -ci saniyədə yanacaq.

İndi, cənab Tomisu bütün dövrələri bir-bir nəzərdən keçirmək istəyir. Hər dövrənin qarşısında o, bir sikkə atacaq (fərz edin ki, bu ədalətli bir sikkədir). Əgər baş gəlirsə, dövrəni seçəcək, əks halda onu rədd edəcək. $n$ -ci dövrəni ziyarət etdikdən sonra cihazı üçün bəzi seçilmiş dövrələr olacaq. Siz ona cihazının gözlənilən ömrünü hesablayaraq kömək etməlisiniz. Əgər heç bir dövrə seçilməzsə, o zaman cihazın ömrü $0$ -dır.

Giriş

Giriş bir tam ədəd $T$ ( $T \leq 100$ T \leq 100) ilə başlayır, bu da test hallarının sayını göstərir.

Hər bir hal bir tam ədəd $n$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100) ilə başlayır, burada $n$ dövrələrin sayını göstərir. Növbəti sətir $n$ boşluqla ayrılmış tam ədədlərdən ibarətdir, burada $i$ -ci tam ədəd $i$ -ci dövrənin yanma dövrünü, $t_{i}$ t_i ( $1 \leq t_{i} \leq 500$ 1 \leq t_i \leq 500) göstərir. Bir test halı üçün bütün yanma dövrlərinin fərqli olduğunu fərz edə bilərsiniz.

Çıxış

Hər bir hal üçün əvvəlcə hal nömrəsini çap edin. Sonra $(r \cdot 2^{n}) mod 10007$ (r \cdot 2^n) \bmod 10007 çap edin, burada $r$ cihazın gözlənilən ömrüdür. Əgər $(r \cdot 2^{n})$ (r \cdot 2^n) tam ədəd deyilsə, dırnaq işarələri olmadan not integer yazın.

Nümunələr

Nümunə 1