C2 - Cykločísla 2

Aďka objavila medzi hračkami jej mamky aj neznámy artefakt. Má zastaralý jednofarebný displej a niekoľko výstupkov so symbolmi.
Obzvlášť ju zaujal ten s označením X^X a začala ho opakovane stláčať. Všimla si, že údaj na displeji veľmi rýchlo rastie, až sa z nejakého dôvodu znova vráti k malým. Vraj to je forma ochrany pred vodou, alebo čo
A keď daný výstupok stlačila veľakrát, začali sa na displeji objavovať čísla, ktoré už predtým boli.
Aďku by zaujímalo, koľko rôznych čísel vie táto vec (vraj sa to volá kalkulačka M7) vygenerovať v závislosti od počiatočného čísla.

Tento model počíta modulo M=2¹⁹-1

Úloha

Pre dané číslo N zistite, koľko rôznych čísel obsahuje postupnosť so začiatkom N

Vstup

V prvom riadku súboru sa nachádza číslo Q udávajúce počet otázok.

Nasleduje Q riadkov s číslom N

M=2¹⁹-1
1 ≤ Q ≤ 1 000
1 ≤ N < M

Výstup

Výstupom programu je odpoveď na každú otázku na samostatnom riadku.

Príklad

Vstup:

2
1
8

Výstup:

1
7