Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Rozważmy następujący proces redukcji danej liczby naturalnej N:
- Jeżeli w zapisie binarnym liczby N w pewnym miejscu występują kolejno cyfry 101, to zmień te cyfry w 1.
- Jeżeli w zapisie binarnym liczby N w pewnym miejscu występują kolejno cyfry 010, to zmień te cyfry w 0.
Przykładowo, liczbę 5 = 101(2) możemy w ten sposób zmienić w liczbę 1, a liczbę 90 = 1011010(2) w 26 = 11010(2) lub 22 = 10110(2). Proces moglibyśmy kontynuować na obu z tych liczb. Dla danej liczby N przez R(N) oznaczmy zbiór wszystkich liczb, do których możemy zredukować liczbę N w dowolnej liczbie kroków. Przykładowo, R(5) = {5, 2}, R(0) = {0} oraz R(90) = {90, 26, 22, 6}.
Twoim zadaniem jest, dla danej liczby K, znaleźć najmniejszą nieujemną liczbę całkowitą NK taką, że |R(NK)| = K. Innymi słowy, należy znaleźć najmniejszą liczbę naturalną taką, że można zredukować ją do dokładnie K liczb. Jako, że N może być bardzo duże, należy wypisać wartość reszty z dzielenia NK przez 998 244 353.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita T oznaczająca liczbę zestawów testowych. W następnych T wierszach następuje opis każdego zestawu testowego, i-ty z nich składa się z jednej liczby całkowitej Ki.
Wyjście
Należy wypisać T wierszy. W i-tym wierszu należy wypisać jedną liczbę, resztę z dzielenia NKi przez 998 244 353.
Ograniczenia
1 ≤ T ≤ 20, 1 ≤ Ki ≤ 1012.
Przykład
| Wejście | Wyjście | |
|
|