package test;
public class Main{
	public static void main(String[] args) {
		int arr[]=new int[20190324];
		arr[0]=1;
		arr[1]=1;
		arr[2]=1;
		for(int i=3;i<20190324;i++) {
			arr[i]=(arr[i-1]+arr[i-2]+arr[i-3])%10000;
			System.out.println((i+1)+" "+arr[i]);
		}
	}
}