//#include <stdio.h>
//void f(int n)
//{
// if(n==0)
// {
// return ;
// }
// f((n)/2);
// printf("%d",n%2);
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// if(n==0)
// {
// printf("0");
// }
// else
// {
// f(n);
// }
// return 0;
//}
//#include <stdio.h>
//void f(int n)
//{
//
// printf("%d\n",n);
// if(n%2==1)
// {
// f(n*3+1);
// }
// if(n==2)
// {
// printf("1");
// return ;
// }
// if(n%2==0)
// {
// f(n/2);
// }
//
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// if(n==1)
// {
// printf("1");
// }
// else{
// f(n);
// }
// return 0;
//}
//#include <stdio.h>
//void f(int n,int k)
//{
// if(n==0)
// {
// return ;
// }
// f(n/k,k);
// if(n%k>=10)
// {
// printf("%c",n%k+55);
// }
// else
// {
// printf("%d",n%k);
// }
//}
//int main()
//{
// int n,k;
// scanf("%d %d",&n,&k);
// f(n,k);
// return 0;
//}
//#include <stdio.h>
//int f(int n)
//{
// if(n==1||n==2)
// {
// return 1;
// }
// return f(n-1)+f(n-2);
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// printf("%d",f(n));
// return 0;
//}
//#include <stdio.h>
//long long int f(long long int n)2 Sec
//{
// if(n<10)
// {
// return n;
// }
// return f(n/10)+n%10;
//}
//int main()
//{
// long long int n;
// scanf("%lld",&n);
// printf("%lld",f(n));
//
// return 0;
//}
//#include <stdio.h>
//int arr[201]={};
//int f(int n)
//{
// if(arr[n]!=0)
// {
// return arr[n]%10009;
// }
// if(n==1||n==2)
// {
// return 1;
// }
// return arr[n]=(f(n-1)+f(n-2))%10009;
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// printf("%d",f(n));
// return 0;
//}
//#include <stdio.h>
//int arr[10000000]={};
//int f(int n)
//{
// if(arr[n]!=0)
// {
// return arr[n];
// }
// if(n==0||n==1||n==2)
// {
// return n;
// }
// if(n==3)
// {
// return 4;
// }
// return arr[n]=(f(n-1)+f(n-2)+f(n-3))%1000;
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// printf("%d",f(n));
// return 0;
//}