using System;

namespace _521_Change
{
	class Program
	{
		static void Main ( string[] args )
		{
			int[] changeArray = { 0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 9, 10, 11, 12, 13, 10, 11, 12, 13, 14, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 9, 10, 11, 12, 13, 10, 11, 12, 13, 14, 5, 6, 7, 8, 9, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 9, 10, 11, 12, 13, 10, 11, 12, 13, 14, 6, 7, 8, 9, 10, 7, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 9, 10, 11, 12, 13, 10, 11, 12, 13, 14, 10, 11, 12, 13, 14, 11, 12, 13, 14, 15 };

			while (true)
			{
				int payment = int.Parse (Console.ReadLine ());

				bool isEnd = payment == 0;

				if (isEnd)
				{
					break;
				}

				int change = changeArray[1000 - payment];

				Console.WriteLine (change);
			}	
		}
	}
}

Measured memory_bytes: 9160