Wstęp do programowania w C++

Jasiu i Stasiu postanowili zagrać w klasy, szybko jednak znudziła im się klasyczna gra, bo nie miała w sobie żadnej strategii. Postanowili zmienić zasady i z gry ruchowo-zręcznościowej uczynić ją grą umysłową. Zasady są proste, Jasiu podaje numer pola, a Stasiu musi odpowiedzieć, na ile sposobów może on dostać się z pierwszego na podane pole, jeśli może przeskakiwać o jedno, dwa lub trzy pola do przodu. Ponieważ liczba sposobów może być liczbą większą niż największa liczba jaką zna Jasiu, Stasiu musi podać ją modulo 1000000009.

Wejście

W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 10^4 ). Każdy przypadek to jedna liczba całkowita n (2 ≤ n ≤ 10^6 ) oznaczająca n-te pole, o które zapytuje Jasiu.

Wyjście

Dla każdego przypadku testowego należy podać liczbę sposobów dostania się z pierwszego na n-te pole, modulo 1000000009.

Example

Input:
2
4
6

Output:
4
13

Z pierwszego na czwarte pole Jasiu może dostać się na cztery sposoby: (1,1,1), (1,2), (2,1), (3).