AlgoLiga 2018

W kombinatoryce rozważamy sposoby podziału obiektów na różne kategorie. Zarówno obiekty jak i kategorie mogą być rozróżnialne, bądź nie. Najtrudniejszym do zliczenia, ale i najciekawszym, przypadkiem jest gdy obiekty i kategorie są nierozróżnialne. Możemy o tym myśleć jako o rozkładzie liczby naturalnej n na sumę dodatnich całkowitych składników. Obiektami w tym przypadku niech będzie n jednakowych piłeczek, a kategoriami - rzędy do których je wkładamy. Kolejność rzędów nie jest istotna. Przydatnym, choć z pozoru trywialnym, narzędziem w zliczaniu takich podziałów są diagramy Ferrersa. Wizualnie przedstawiają one właśnie piłeczki ustawione w rzędach z narzuconą kolejnością - rzędy są posortowane względem liczby piłeczek.

Przykładowo możemy bez trudu udowodnić, że liczba podziałów n na nie więcej niż k składników jest równa liczbie podziałów n+k na dokładnie k składników. Do każdego diagramu, który reprezentuje podział liczby n na nie więcej niż k składników, dostawiamy kolumnę k piłeczek. Otrzymujemy wtedy podział liczby n+k na dokładnie k składników. Takie przyporządkowanie jest wzajemnie jednoznaczne.

Nie jest łatwe policzenie wszystkich podziałów n, ale możemy rozważać szczególne podziały liczby dla których to zadanie jest łatwiejsze. Ciekawym przypadkiem podziału liczby jest jej rozkład na sumę kolejnych liczb naturalnych, co jest przedmiotem tego zadania.

Wejście

Wejście rozpoczyna się liczbą t<=1000 oznaczającą ilość przypadków testowych. Każdy przypadek testowy składa się z jednej liczby 1<=n<=10⁶.

Wyjście

Dla każdego przypadku testowego należy wypisać w osobnej linii ilość podziałów liczby n na składniki będące kolejnymi liczbami naturalnymi.

Przykład

Wejście:
3
1
2
3

Wyjście:
1
1
2


Objaśnienie do przykładu - liczbę 3 możemy przedstawić na dwa sposoby jako sumę kolejnych liczb naturalnych:
3
1 + 2