import java.awt.Point;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Dollars
{
    /*
     * Amount of bills and coins, sorted from largest to smallest amount.
     */
    private static final int[] AMOUNTS = { 10000, 5000, 2000, 1000, 500, 200, 100, 25, 10, 5, 1 }; 
    
    /*
     * Memorizes already computed values of number(amount, index).
     * The pair (amount, index) is represented as a Point.
     */
    private static Map<Point, Long> memory = new HashMap<Point, Long>();
    
    /*
     * The number of ways to make up the given amount with bills and
     * coins whose index in Dollars.COINS greater than or equal to
     * the given index.
     * 
     * @param amount the amount to be made up.
     * @pre. amount > 0
     * @param index index in Dollars.COINS
     * @pre. index >= 0 && index < Dollars.COINS
     * @return number of ways to make up the given amount with bills and
     * coins whose index in Dollars.COINS greater than or equal to
     * the given index.
     */
    private static long number(int amount, int index)
    {
	long number;
	if (index == Dollars.AMOUNTS.length - 1)
	{
	    number = 1;
	}
	else
	{
	    Point point = new Point(amount, index);
	    Long value = memory.get(point);
	    if (value == null)
	    {
		number = 0;
		long times = amount / Dollars.AMOUNTS[index];
		for (int i = 0; i <= times; i++)
		{
		    number += Dollars.number(amount - i * Dollars.AMOUNTS[index], index + 1);
		}
		memory.put(point, number);
	    }
	    else
	    {
		number = value.longValue();
	    }
	}
	return number;
    }

    public static void main(String[] args)
    {
	PrintStream output = System.out;
	Scanner input = new Scanner(System.in);
	
	int amount = input.nextInt();
	while (amount != 0)
	{
	    output.println(Dollars.number(amount, 0));
	    amount = input.nextInt();
	}
    }
}