Gra w karty

Ulubionym zajęciem na planecie Mamlaków jest gra w karty. Talia kart składa się z 1 000 000 000 kart ponumerowanych od 1 do 1 000 000 000 (numery kart nie powtarzają się). Numer karty określa ilość punktów do niej przypisanych. Liczba kart jakie otrzymuje zawodnik jest dowolna (zawodnik deklaruje ile chce otrzymać kart od rozdającego), jednak punkty zdobywa tylko wtedy, kiedy w jego posiadaniu znajdą się wyłącznie karty o kolejnych numerach. Suma przyznawanych punktów jest równa sumie punktów przypisanych do poszczególnych kart.

Weźmy dla przykładu liczbę punktów równą 21. Taką liczbę punktów można uzyskać na cztery sposoby:

• Pobieramy sześć kart i będą to karty o numerach: 1, 2, 3, 4, 5, 6.
• Pobieramy trzy karty i będą to karty o numerach: 6, 7, 8.
• Pobieramy dwie karty i będą to karty o numerach: 10, 11.
• Pobieramy tylko jedną kartę i bedzie to karta o numerze: 21.

Twoim zadaniem jest napisanie programu, który wyznaczy ile jest różnych sposobów uzyskania zadanej liczby punktów.

Dane wejściowe:

W pierwszym wierszu wejścia znajduje się jedna liczba N będąca liczbą zestawów danych. W kolejnych N wierszach znajdują się kolejne zestawy danych.

Opis jednego zestawu danych składa się z jednego wiersza i zawiera jedną liczbę M (1 ≤ M ≤ 1 000 000 000) będącą liczbą punktów jakie chcemy uzyskać w grze.

Dane wyjściowe:

Dane wyjściowe składają się z N wierszy. Jeden wiersz odpowiada jednemu zestawowi danych wejściowych i zawiera liczbę określającą na ile sposobów można uzyskać w grze M punktów.

Przykładowe dane wejściowe:

6
21
8
45
81
18
59
        

Przykładowe dane wyjściowe:

4
1
6
5
3
2