Problem

Magicpig and Kinfkong come to like playing cards recently. Magicpig knows that Kinfkong is very good at mathematics, so he often asks Kinfkong some very hard problems in order to baffle him. You know, Kinfkong is very clever, so he can defeat Magicpig each time.

One day, Magicpig takes out a pile of n cards and asks Kinfkong a question: "Now I have n cards in my hand. We do't care about the face value of the cards, so we consider them to be the same. Now you can take some cards from my hand. Each time you can take 1,2 or 3 cards. Repeat this step until there is no more card in my hand. Now I want to know how many different ways can you take away all the cards from my hand. I give you 10 minutes. If you can't figure out the answer, you are defeated."

You are a friend of Kinfkong. Now Kinfkong can not figure out the answer and there is no time left! He knows you are an excellent ACMer, so he needs you help!

Input


The input contains one or more data sets. Each data set consists of a positive integer n(<=500), denoting the number of cards.
A line which contains a single 0 will end the input.


Output


One number on each line, the number of distinct ways to take away all the cards in Magicpig's hand.

Sample Input

1
2
3
0

Sample Output


1
2
4

Author: Mathematica