#include<stdio.h>

int Coin[] = {500,100,50,20, 10, 5,2,1};

int nway[1001];



void Count() {
	int i, n, j, c;
	nway[0] = 1;
	for(i = 0; i<=7; i++) {
		c = Coin[i];
		for(j = c; j<=1000; j++) {
			nway[j] += nway[j-c];
		}
	}
}

int main() {
	int n;
	Count();
	while(scanf("%d",&n) && n) { // n must be smaller than 1001
		printf("%d\n",nway[n]);
	}
	return 0;
}