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. Jednym z młodych informatyków poszukujących pracy jest pan Jan. Po długich poszukiwaniach, w końcu jeden z szefów wielkich korporacji postanowił dać szansę panu Janowi. Obiecał mu posadę jeśli ten odpowie na pytanie: "iloma pracownikami zarządzam?". Pan Jan wie że w tej firmie panuje dość specyficzna hierarchia kadrowa: najniżej są zwykli pracownicy, wyżej w hierarchii są szefowie 1 stopnia, jednak rządzą oni tylko jednym "robolem". Później są szefowie 2 stopnia, zarządzają oni jednym zwykłym robolem oraz jednym szefem 1 stopnia. Każdy szef N-tego stopnia (N>2) zarządza jednym szefem stopnia N–1 i jednym szefem stopnia N–2. Przykładowo szef 3-go stopnia ma pod sobą 6 pracowników: 1 szefa stopnia 2, 2 szefów stopnia 1 oraz 3 zwykłych pracowników.
Dodatkowo, w celu ułatwienia rozwiązania tego trudnego zadania, Prezes (naczelny szef, z którym pan Jan rozmawiał) zdradził, że jest szefem K-tego stopnia oraz powiedział, że wystarczy jak otrzyma 9 ostatnich cyfr wyniku (ze względu na dużą liczbę pracowników). Twoim zadaniem jest napisanie programu, który pomoże uzyskać odpowiedź na tak postawione pytanie.
W pierwszej linii znajduje się liczba D, oznaczająca liczbę zestawów danych. Każdy test składa się liczby całkowitej K (1≤K≤109) umieszczonej w osobnej linii, będącej stopniem Prezesa.
Dla każdego zestawu danych wypisz ostatnie dziewięć cyfr liczby zatrudnionych pracowników we wspomnianej wielkiej korporacji. W razie gdyby ta liczba nie miała 9 cyfr, należy ją poprzedzić zerami wiodącymi.
3
1
5
1000
000000001
000000019
496035875