Je pondelňajšie ráno a Kubo sa vyvaľuje na gauči v T21. Aby zvládol náročný týždeň sedenia na prednáškach, v batohu si so sebou dovliekol hromadu čokolád. V momente, ako začal jednu rozbaľovať, dvere do T2 sa otvorili a zjavili sa v nich Vlejd s Baškou. Sotva zračili fialový obal, div si neoslintali svoje krásne nové KSP tričká.
Kubovi bolo teda hneď jasné, že sa bude musieť o čokolády deliť. Kubo je krásny, spravodlivý a prajný, preto sa chce deliť rovnomerne. Rýchlo v hlave prerátal, koľko dielikov treba každému z nich troch ulomiť, no skôr ako stihol čokoládu prerozdeliť, dvere sa rozleteli znova a vošla Šandyna s Jarom. Celý proces slintania a prerátavania sa zopakoval, no to sa už do T2-ky tlačil Adam s Dendou. Kubo, vidiac tento nemilý trend, začal premýšľať.
Koľko najviac vedúcich môže ešte do T2 prísť po dvojiciach tak, aby im mohol (vrátane seba) spravodlivo rozdeliť čokoládu?
Úloha
Keďže vedúci prichádzajú do T2 po dvojiciach, spolu s Kubom ich bude vždy nepárny počet. Každá z Kubových čokolád má nejaký počet dielikov (označme ho \(n\)), ktoré by chcel (teda, už musí :) ) rovnomerne prerozdeliť spravodlivo medzi seba a zvyšných vedúcich. Zaujíma ho najväčší možný počet vedúcich, pre ktorý sa čokoláda ešte dá rozdeliť. A vy mu s tým máte pomôcť.
Formát vstupu
Na prvom riadku sa nachádza číslo \(q\) – počet čokolád, ktoré má Kubo v batohu. Nasleduje \(q\) riadkov, pričom \(i\)-ty z nich obsahuje číslo \(n_i\) – počet dielikov \(i\)-tej čokolády. Pre jednotlivé testovacie sady sú horné limity pre \(q\) a \(n_i\) dané nasledujúcou tabuľkou:
| číslo sady | \(1\) | \(2\) | \(3\) | \(4\) |
|---|---|---|---|---|
| \(1 \leq n_i \leq\) | \(2^{16}\) | \(2^{32}\) | \(2^{60}\) | \(2^{60}\) |
| \(1 \leq q \leq\) | \(100\) | \(500\) | \(1\,000\) | \(10\,000\) |
(Nezabudnite použit 64bitové premenné. V C++ long long, v Pascale Int64, v Jave long)
Formát výstupu
Pre každú čokoládu vypíšte jeden riadok obsahujúci najväčší (nepárny) počet vedúcich, medzi ktorých sa dá čokoláda rozdeliť rovnomerne.
Príklady
Input:
3
24
60
1Output:
3
15
1Čokoládu s 24 dielikmi vieme rovnomerne rozdeliť medzi troch vedúcich (každému dáme 8 dielikov). Čokoládu s 60 dielikmi vieme rozdeliť medzi pätnástich (každému dáme 4 dieliky). Čokoláda s jedným dielikom sa nedá deliť, takže ju Kubo musí zjesť, keď bude niekde sám.
T2 je KSP-ácka miestnosť na matfyze↩
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.