Card game P54504

You are playing a card game with a friend. For this game only the suit of the cards matters. The four suits are clubs, diamonds, hearts and spades, with the following values:

Your friend selects a number n, and you must show cards whose total value equals n, by using the minimum possible number of cards. Assume that you have an unlimited number of cards of each suit.

Input

Input consists of several cases, each one with a natural number n between 0 and 500000. Input ends with a −1.

Output

For every n, print the corresponding result.