Sparing w Programowaniu Zespołowym UAM & PP, 6.11.2004

Opis

Jak już zapewne wielu z Was wie w roku 2223 nastąpiło nasycenie rynku pracy informatykami. Wielu absolwentów informatyki nie może znaleźć pracy, zaś starzy boją się o swoje posady. Dlatego też chcąc zdobyć intratną posadę w firmie Microhard jesteś gotów zrobić wszystko. Widząc twój zapał prezes postanowił Cię wykorzystać przy corocznym spisie pracowników. Od niedawna w firmie panuje nowa hierarchia dowodzenia w związku z czym mało kto może się doliczyć ilu ludzi w sumie pracuje w firmie. Wiadomo, że najniżej w hierarchii stoją zwykli robotnicy. Wyżej od nich są szefowie 1-stopnia którzy rządzą 2 zwykłymi "robolami". Ponad nimi stoją szefowie 2-stopnia którzy rządzą 2 szefami 1 stopnia i jednym zwykłym robotnikiem. Ponad nimi są szefowie 3-stopnia którzy rządzą 2 szefami 2 stopnia i jednym szefem 1 stopnia. Podobnie jest z szefami wyższych stopni - każdy szef N-tego stopnia ma pod sobą 2 pracowników N-1 stopnia oraz 1 pracownika N-2 stopnia. Twoim zadaniem jest stwierdzenie ilu zwykłych roboli ma pod sobą pracownik stopnia N. Chcą Ci ułatwić trochę zadanie wystarczy, że podasz 9 ostatnich cyfr otrzymanego wyniku.

Specyfikacja wejścia

W pierwszej linii znajduje się liczba D, oznaczająca liczbę zestawów danych. Każdy test składa się liczby całkowitej N (1 ≤ N ≤ 10^9) umieszczonej w osobnej linii.

Specyfikacja wyjścia

Dla każdego zestawu danych w osobnej linii wypisz ostatnie dziewięć cyfr liczby zatrudnionych pracowników we wspomnianej wielkiej korporacji.

Przykład

3
1
5
3

2
70
12