/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
int m = 1;
void rec(int n)
{
if(n==0)
{
return;
}
rec(n-1);
m *= n;
return;
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
printf("%d",m);
}
*/
/*
#include <stdio.h>
int rec(int n)
{
if(n == 1 || n == 2)
{
return 1;
}
else
{
return rec(n-1)+rec(n-2);
}
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",rec(n));
}
*/
/*
#include <stdio.h>
int n;
int rec(int n)
{
printf("%d\n",n);
if(n%2==1)
{
if(n != 1)
{
return rec(3*n+1);
}
else
{
return;
}
}
rec(n/2);
return;
}
int main()
{
scanf("%d",&n);
rec(n);
}
*/
/*
#include <stdio.h>
int rec(int n)
{
if(n%2==1)
{
if(n!=1)
{
rec(3*n+1);
}
else
{
printf("1\n");
return;
}
}
else
{
rec(n/2);
}
printf("%d\n",n);
return;
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
}
*/
/*
#include <stdio.h>
int s;
int SuperSum (int k, int n)
{
if(k == 0)
{
s+=n;
return n;
}
else
{
for(int i = 1; i<=n ; i++)
{
SuperSum(k-1,i);
}
}
return s;
}
int main()
{
int k, n;
while( scanf("%d %d", &k, &n) != EOF )
{
s = 0;
printf("%d\n", SuperSum(k, n));
}
}
*/
/*
#include <stdio.h>
int s = 0;
void rec(int n)
{
if(n == 0)
{
return;
}
rec(n-1);
s += n;
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
printf("%d",s);
}
*/
/*
#include <stdio.h>
void rec(int n)
{
if(n == 0)
{
return;
}
rec(n-1);
printf("*");
}
void star(int n)
{
if(n == 0)
{
return;
}
star(n-1);
rec(n);printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
star(n);
}
*/
/*
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
printf("%d",n%100000000);
}
*/
/*
#include <stdio.h>
int rec(int n)
{
printf("%d\n",n);
if(n%2==1)
{
if(n != 1)
{
rec(3*n+1);
}
else
{
return;
}
}
else
{
rec(n/2);
}
return;
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
}
*/
/*
#include <stdio.h>
int rec(int n)
{
if(n%2==1)
{
if(n != 1)
{
rec(3*n+1);
}
else
{
printf("1\n");
return;
}
}
else
{
rec(n/2);
}
printf("%d\n",n);
return;
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
}
*/