POLSKI SPOJ

Trójkąty

Jasio jako bardzo zdolny uczeń postanowił uczęszczać na dodatkowe zajęcia z matematyki. Lekcje niezwykle mu się spodobały. Na koniec jednej z nich pani profesor przedstawiła zadanie domowe.

Narysowała na tablicy trójkąt równoboczny o boku=1. Następnie narysowała kolejny trójkąt równoboczny o boku=2 i podzieliła go na mniejsze części które były trójkątami równobocznymi o boku=1. Uczyniła to samo z kolejnym trójkątem. I zadała pytanie: ile wszystkich trójkątów możemy zaobserwować w trójkącie o boku n?

Jasio jest bardzo inteligentnym chłopcem i dość szybko wpadł na pomysł rozwiązania problemu. Wracając do domu rozmyślał jednak jak sprawdzić poprawność otrzymanych wyników. Ty jako starszy brat Jasia postanowiłeś pomóc mu w tym trudnym zadaniu.

Napisz program w którym określisz ile trójkątów można znaleźć w zadanym trójkącie o boku n.

Wejście:

W pierwszym wierszu jedna liczba k określająca ilość zestawów danych (k< 10^{^6}).

Każdy zestaw składa się z jednej liczby n, przedstawiającej numer figury (0 ≤ n ≤ 10^{^9}).

Wyjście:

Jedna liczba będąca odpowiedzią na zadane pytanie dla trójkąta o boku n. Wynik przedstaw modulo 10101.

Przykład:

Wejście:
3
1
2
10

Wyjście:
1
5
315