Wstęp do programowania w C++

Na pewnej planecie, której nazwy nie pamiętam, rozróżniamy dwa rodzaje żyjątek: Zera i Jedynki. Na początku było ich bardzo dużo. Tylko Jedynki są zdolne do rodzenia swoich potomków i mogą to robić nawet w sytuacji, gdy nie mają partnera czyli Zera do pary (jedynki mają tylko jednego potomka przez całe swoje życie), ale wtedy rodzi się tylko żyjątko płci Zero. Jeśli natomiast Jedynka ma partnera, to w takiej sytuacji rodzi się następna Jedynka. Twoim zadaniem jest określenie, ilu wszystkich przodków swojej płci ma Zero urodzone w n-tym pokoleniu. Przyjmujemy, że pierwsi przodkowie to pokolenie numer 0.

Wejście

W pierwszym wierszu jedna niewielka liczba określająca ilość zestawów danych (nie więcej niż 100 000).

Każdy zestaw składa się z jednej liczby n, przedstawiającą numer pokolenia Zera (0 ≤ n ≤ 100000).

Wyjście

Dla każdego zestawu liczba przodków żyjątka płci Zero urodzonego w n-tym pokoleniu, które są także Zerami. Wynik przedstaw modulo 1010101010101.

Przykład

Wejście:
2
3
5

Wyjście:
2
7