/*#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i;
int arr[10001] = {};
arr[0] = arr[1] = 1;
scanf("%d", &n);
for (i = 2; i < n; i++)
{
arr[i] = arr[arr[i-1]-1] + arr[i-arr[i-1]];
}
printf("%d", arr[n - 1]);
return 0;
}
*/
/*#include<stdio.h>
void sub(int k) {
if(k==0) {
return;
}
printf("%d\n", k);
sub(k-1);
}
int main() {
int n;
scanf("%d", &n);
sub(n);
}
/*
sub(5) {
sub(4) {
sub(3) {
// stack
}
}
}
*/
/*#include<stdio.h>
void function(int i)
{
if(i==0)
{
return;
}
function(i-1);
printf("%d\n",i);
}
int main()
{
int n;
scanf("%d",&n);
function(n);
}*/
/*#include<stdio.h>
void f(int k)
{
if(k==0)
{
return;
}
printf("%d\n",k);
f(k-1);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
}*/
/*#include<stdio.h>
void f(int k,int i)
{
if(k>i)
{
return;
}
if(k%2!=0)
{
printf("%d ",k);
}
f(k+1,i);
}
int main()
{
int a,b;
scanf("%d %d",&a,&b);
f(a,b);
}*/
/*#include<stdio.h>
int f(int k)
{
if(k==0)
{
return 0;
}
return k+f(k-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}*/
/*
#include<stdio.h>
int f(int k)
{
if(k==1)
{
return k;
}
return k*f(k-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
// non-linearity recursion function
// memoization
/*#include<stdio.h>
int rec(int k) {
if() {
return 0;
}
return rec(k-1) + rec(k-2);
}
int main() {
sadsa
}*/
// 1915 1953 1928 1920
// 1916 3702 3733
/*#include<stdio.h>
int f(int k)
{
if(k==1||k==2)
{
return 1;
}
return f(k-1)+f(k-2);
}
int main()
{
int N;
scanf("%d",&N);
printf("%d",f(N));
}*/
/*#include<stdio.h>
void star(int k)
{
if(k==0)
{
return;
}
star(k-1);
printf("*");
}
void f(int k)
{
if(k==0)
{
return;
}
f(k-1);
star(k);
printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
f(n);
}*/
/*#include<stdio.h>
void f(int k)
{
if(k==1)
{
return;
}
if(k%2==1)
{
k=k*3+1;
printf("%d\n",k);
}
else if(k%2==0)
{
k=k/2;
printf("%d\n",k);
}
f(k);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",n);
f(n);
}
*/