W czasach młodości kapitan Mambeks był kadetem międzygalaktycznej szkoły nawigatorów. Pewnego razu na zajęciach z algebry miał obliczyć dwie ostatnie cyfry z 21321446 liczby w ciągu Fiboncciego. Kapitan rozwiązał ten program pisząc krótki program. Teraz syn jednego z kolegów Kapitana ma ten sam problem. Niestety kapitan skasował program, i kompletnie nie pamięta żadnych szczegółów. Pomóż kapitanowi napisać ten Program.
Ciąg fibonacciego jest zdefiniowany następująco:
f(1) = f(2) = 1
f(n) = f(n - 1) + f(n - 2)
Dane wejściowe:
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych n ( n >= 0 i n <= 20000). W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. Każdy zestaw składa się z jednego wiersza w którym jest zapisana jedna liczba m (m > 0 i m <= 2000000000).
Dane wyjściowe:
Dla każdego zestawu danych wejściowych program ma wypisać dwie ostatnie cyfry liczby f(m). Program nie powinien wypisywać wiodących zer.
Przykładowe dane wejściowe:
3
1
7
401
Przykładowe dane wyjściowe:
1
13
1