/*
#include <stdio.h>
int main()
{
int a, i, b=0;
scanf("%d", &a);
for(i=2 ; i<a ; i+=1)
{
if(a%i==0)
{
b=1;
}
}
if(b==1)
{
printf("not prime");
}
else
{
printf("prime");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a, i;
scanf("%d", &a);
for(i=1 ; i<=a ; i+=1)
{
if(a%i==0)
{
printf("%d ", i);
}
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int k, h;
scanf("%d %d", &k, &h);
if(k%2==0)
{
k=k/2*10;
}
else
{
k=k/2+1;
}
if(h%2==0)
{
h=(h/2)*10;
}
else
{
h=h/2+1;
}
printf("%d", k+h);
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int a, b, i;
int max=0;
scanf("%d", &a);
for(i=0; i<a; i++)
{
scanf("%d", &b);
if(b>max)
{
max=b;
}
}
printf("%d", max);
}
*/
/*
#include<stdio.h>
int main()
{
int n, k, t, i;
scanf("%d", &n);
for(i=0 ; i<=n ; i++)
{
if(i*i>=n)
{
printf("%d ", n-(i-1) * (i-1));
printf("%d", i-1);
break;
}
}
}
*/
/*
#include<stdio.h>
int main() {
int n;
int k, s=0, i;
scanf("%d", &n);
for(i=0; i<n; i++) {
scanf("%d", &k);
s+=k;
}
printf("%d", s);
}
*/
/*
#include<stdio.h>
int main()
{
int a, b=0, n, i;
scanf("%d", &n);
for(i=0 ; i<n; i++)
{
scanf("%d", &a);
if(a%5==0)
{
b+=a;
}
}
printf("%d", b);
}
*/
/*
#include<stdio.h>
int main()
{
int n, i, a, b=0;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a);
if(a%2!=0)
{
b+=1;
}
}
printf("%d", b);
}
*/
/*
#include<stdio.h>
int main()
{
int a, b, c=0, i;
scanf("%d %d", &a, &b);
for(i=a; i<=b; i++)
{
if(i%2!=0)
{
c+=i;
}
else
{
c-=i;
}
}
printf("%d", c);
}
*/
/*
#include<stdio.h>
int main()
{
int a, b, c=0, i;
scanf("%d %d", &a, &b);
for(i=a; i<=b; i++)
{
if(i%2!=0)
{
c+=i;
printf("+%d", i);
}
else
{
c-=i;
printf("-%d", i);
}
}
printf("=%d", c);
}
*/
/*
#include<stdio.h>
int main()
{
int a, b, c=0, i;
scanf("%d %d", &a, &b);
for(i=a; i<=b; i++)
{
if(i%2==0)
{
c-=i;
printf("-%d", i);
}
else
{
c+=i;
if(i==a)
{
printf("%d", i);
}
else
{
printf("+%d", i);
}
}
}
printf("=%d", c);
}
*/
/*
#include<stdio.h>
int main() {
int x, y;
int i, j;
int n;
scanf("%d", &n);
for(i=0; i<n; i++) { // 세로
for(j=0; j<n; j++) { // 가로
printf("(%d,%d)\t", i, j);
}
printf("\n");
}
}
*/
// 사각형 출력하기 1, 2, 3, 4
// 주의: 1번을 다 풀때까지 2번 보지 않기
/*
#include<stdio.h>
int main()
{
int n, i, j;
scanf("%d", &n);
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
printf("*");
}
printf("\n");
}
}
*/
/*
#include<stdio.h>
int main()
{
int a=1, b=1, i, j, n;
scanf("%d", &n);
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(a==1||a==n||b==1||b==n)
{
printf("*");
}
else
{
printf(" ");
}
b++;
}
printf("\n");
a++;
b=1;
}
}
*/
/*
#include<stdio.h>
int main()
{
int a=1, b=1, c=1, i, j, n;
scanf("%d", &n);
int d=n;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(a==1||a==n||b==1||b==n||a&&b==c||a&&b==d)
{
printf("*");
}
else
{
printf(" ");
}
b++;
}
printf("\n");
c++;
d-=1;
a++;
b=1;
}
}
*/
/*
#include<stdio.h>
int main()
{
int a=1, b=1, c=1, i, j, n;
scanf("%d", &n);
int d=n, e=(n/2)+1;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(a==1||a==n||b==1||b==n||a&&b==c||a&&b==d||a==e||b==e)
{
printf("*");
}
else
{
printf(" ");
}
b++;
}
printf("\n");
c++;
d-=1;
a++;
b=1;
}
}
*/
/*
#include<stdio.h>
int main()
{
int n, m, i, j, a=1, b=1;
scanf("%d %d", &m, &n);
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(a==1&&b==1||a==1&&b==m||a==n&&b==1||a==n&&b==m)
{
printf("+");
}
else if(a==1||a==n)
{
printf("-");
}
else if(b==1||b==m)
{
printf("|");
}
else
{
printf(" ");
}
b++;
}
printf("\n");
a++;
b=1;
}
}
*/