2-nin bölənləri

Təbii ədəd x üçün f(x) funksiyası, x ədədini dəqiq bölən ən kiçik təbii ədədi göstərir. Məsələn, f(1) = 1, f(5) = 16, f(6) = 12.

Verilmiş tam qeyri-mənfi k ədədi üçün f(2^k) mod 99999640000243 hesablayın.

Giriş verilənləri

Giriş faylının ilk sətirində təbii ədəd T (1 ≤ T ≤ 10^5) - testlərin sayı verilir. Sonrakı T sətirdə hər birində tam ədəd k (1 ≤ k ≤ 10^18) verilir.

Çıxış verilənləri

Giriş faylındakı hər bir k üçün ayrıca sətirdə f(2^k) mod 99999640000243 ədədini çıxarın.

Nümunələr