/*#include <stdio.h>
int n, m, x, a, b, cnt=-1, dab=10000000;
char arr[100][100];
int kekeke[100][100]={};
char heehee[100][100], gyungro[1000];
int queue[100][2], hehehe[1000], d=1, l=1, visited[100][100]= {}, visit[10000], gt=0;
int front=0, rear=0;
void bfs(int p, int q)
{
int i, j;
if(visited[p][q]==1)
return ;
kekeke[p][q]=cnt;*/
/*for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
printf("%c ",arr[i][j]);
}
printf("\n");
}
printf("%d %d %d\n\n\n",p,q,cnt);*/
/*if(p==a&&q==b)
{
if(cnt<dab)
dab=cnt;
return ;
}
visited[p][q]=1;
if(arr[p+1][q]!='F'&&visited[p+1][q]==0&&p+1>=0&&q>=0&&p+1<n&&q<m)
{
heehee[p+1][q]='U';
queue[++rear][0]=p+1;
queue[rear][1]=q;
}
if(arr[p-1][q]!='F'&&visited[p-1][q]==0&&p-1>=0&&q>=0&&p-1<n&&q<m)
{
heehee[p-1][q]='D';
queue[++rear][0]=p-1;
queue[rear][1]=q;
}
if(arr[p][q+1]!='F'&&visited[p][q+1]==0&&p>=0&&q+1>=0&&p<n&&q+1<m)
{
heehee[p][q+1]='L';
queue[++rear][0]=p;
queue[rear][1]=q+1;
}
if(arr[p][q-1]!='F'&&visited[p][q-1]==0&&p>=0&&q-1>=0&&p<n&&q-1<m)
{
heehee[p][q-1]='R';
queue[++rear][0]=p;
queue[rear][1]=q-1;
}
}
void fire()
{
int i, j, brr[100][2], g=0;
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(arr[i][j]=='F')
{
brr[++g][0]=i;
brr[g][1]=j;
}
}
}
for(int i=1; i<=g; i++)
{
arr[brr[i][0]+1][brr[i][1]]='F';
arr[brr[i][0]][brr[i][1]+1]='F';
arr[brr[i][0]-1][brr[i][1]]='F';
arr[brr[i][0]][brr[i][1]-1]='F';
}
}
int abs(int a)
{
if(a<0)
return a;
return a;
}
void huhuhu()
{
int t, y;
int i, j, k;
for(i=dab;i>=1;i--)
{int kkk=0;
for(j=0;j<n;j++)
{
for(k=0;k<m;k++)
{
if(kekeke[j][k]==i&&kkk==0*//*&&abs(t-j)+abs(y-k)<=2*//*)
{gyungro[++gt]=heehee[j][k];
kkk++;*/
//t=j;
//y=k;
/*}
}
}
}
for(i=gt;i>=1;i--)
{
if(gyungro[i]=='D')
printf("U");
else if(gyungro[i]=='L')
printf("R");
else if(gyungro[i]=='R')
printf("L");
else if(gyungro[i]=='U')
printf("D");
}
printf("\n");
}
int main()
{
scanf("%d %d %d\n", &n, &m, &x);
int i, j;
for(i=0; i<n; i++)
scanf("%s",arr[i]);
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(arr[i][j]=='Y')
{
queue[++rear][0]=i;
queue[rear][1]=j;
}
if(arr[i][j]=='E')
{
a=i;
b=j;
}
}
}
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
heehee[i][j]='O';
}
}
while(front!=rear)
{
cnt++;
if(cnt%x==0&&cnt!=0)
fire();
l=rear;
int u=front+1;
for(i=u; i<=l; i++)
{
int r=queue[++front][0];
int t=queue[front][1];
bfs(r, t);
}
}
printf("%d\n", dab);
huhuhu();
*/
/*for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
printf("%c ",heehee[i][j]);
}
printf("\n");
}*/
//}
/*
5 5 2
FOOOE
OOOOO
OOOOO
OOOOO
YOFFO
*/
/*
4 0 0
4 1 1
3 1 2
2 1 3
2 2 4
1 2 5
1 3 6
1 4 7
0 4 8*/
/*
#include <stdio.h>
int gcd(int a, int b)
{
if(b==0)
return a;
return gcd(b, a%b);
}
int main()
{
int t, i, j;
scanf("%d", &t);
for(i=0; i<t; i++)
{
int n, cnt=0;
scanf("%d", &n);
int a, b;
for(a=2; a<=n; a++)
{
for(b=1; b<a; b++)
{
if(gcd(a, b)==1)
{
cnt++;
printf("찾은 기약 분수 : %d/%d\n", b, a);
}
}
}
printf("찾은 기약 분수 : %d/%d\n", 1, n);
printf("찾은 기약 분수 : %d/%d\n", n, 1);
printf("총 %d개의 기약 분수가 존재합니다.", cnt+2);
}
}
*/
#include <stdio.h>