#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;

string move1(string s)
{
    string a;
    for(int i = 7 ; i >= 4; i -- )  a += s[i];
    for(int i = 3 ; i >= 0; i -- )  a += s[i];
    return a;
}

string move2(string s)
{
    string a;
    a += s[3];
    for(int i = 0 ; i < 3 ; i ++ )  a += s[i];
    for(int i = 5 ; i <= 7 ; i ++ ) a += s[i];
    a += s[4];
    return a;
}

string move3(string s)
{
    string a;
    a = s;
    char t = a[1];
    a[1] = a[6], a[6] = a[5], a[5] = a[2], a[2] = t;
    return a;
}


int bfs(string start, string end)
{
    if( start == end )  return 0;
    queue<string> q;
    q.push(start);
    while(q.size())
    {
        string t = q.front();
        q.pop();
        string m[4];
        m[1] = move1(t);
        m[2] = move2(t);
        m[3] = move3(t);
        for(int i = 1; i <= 3 ; i ++)
        {
            if( dist[m[i]] == 0 )
            {
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {'A' + i - 1, t};
                q.push(m[i]);
                if( m[i] == end )   return dist[end];
            }
        }
    }
    return -1;
}


int main()
{
    string end, start = "12345678";
    for(int i = 1; i <= 8 ; i ++ )
    {
        int x;
        cin >> x;
        end += x + '0';
    }
    int t = bfs(start, end);
    cout << t << endl;
    string a;
    while( end != start )
    {
        a += pre[end].first;
        end = pre[end].second;
    }
    reverse(a.begin(),a.end());
    cout << a ;
    return 0;
}

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e3 + 10;
char g[N][N];
int dist[N][N];
int n, m;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
void bfs()
{
    queue<PII> q;
    for(int i = 1; i <= n; i++ )
    {
        for(int j = 1; j <= m ; j++ )
        if( g[i][j] == '1' )
        {
          //  cout << i << ' ' << j << endl;
            dist[i][j] = 0;
            q.push({i,j});
        }
        else
            dist[i][j] = -1;
    }

    while( q.size() )
    {
        PII t = q.front();
        q.pop();
        for(int i = 0 ; i < 4 ; i++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if( x >= 1 && x <= n && y >= 1 && y <= m && dist[x][y] == -1 )
                dist[x][y] = dist[t.first][t.second] + 1, q.push({x,y});
        }
    }

}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++ )
        for(int j = 1; j <= m; j ++ )
                cin >> g[i][j];
    bfs();
    for(int i = 1; i <= n; i++ )
    {
        for(int j = 1; j <= m ; j ++ )
            cout << dist[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int dist[N];
int n, m;

void bfs(int x)
{
    memset(dist,-1,sizeof dist);
    dist[x] = 0;
    queue<int> q;
    q.push(x);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        if( t - 1 >= 0 && dist[t - 1] == - 1 )
            q.push(t-1), dist[t-1] = dist[t] + 1;
        if( t + 1 <= m && dist[t + 1] == -1 )
            q.push(t+1), dist[t+1] = dist[t] + 1;
        if( t * 2 <= m + 1  && dist[t*2] == -1 )
            q.push(t*2),dist[t*2] = dist[t] + 1;
    }

}


int main()
{
    cin >> n >> m;
    bfs(n);
    cout << dist[m] << endl;
    return 0;
}

#include <iostream>
using namespace std;
int main()
{
    int n;
    while( cin >> n )
    {
        int cnt = -1;
        for(int i = 11 ; i < n ; i += 10 )
        {
       // int t = i;
         bool t = false;
         for(int j = 2 ; j <= i / 2 + 1 ; j ++ )
                if( i % j == 0 )
                t = true;
        if ( !t )
            cout << i << ' ',cnt ++ ;
        }
        if( cnt == -1 ) cout << -1 ;
        cout << endl;
    }

    return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int t, p = 1;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int a[n+1];
        for(int i = 1; i <= n; i++ )    cin >> a[i];
        int res = 0;
        for(int i = 2 ;i < n ; i++ )
            if( a[i] > a[i-1] && a[i] > a[i+1])
                res ++ ;
        printf("Case #%d: %d\n",p++,res);
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;

int dx[] = {-2,-2,-1,-1,1,1,2,2};
int dy[] = {-1,1,-2,2,-2,2,-1,1};

const int N = 160;
char s[N][N];
PII st[N][N];
int n, m;


void bfs(int sx, int sy)
{
    queue<PII> q;
    q.push({sx,sy});
    memset(st, -1, sizeof st);
    st[sx][sy] = {0,0};
    while( q.size() )
    {
        PII t = q.front();
        q.pop();
        for(int i = 0 ; i < 8 ; i ++ )
        {
            int xx = t.x + dx[i], yy = t.y + dy[i];
            if( xx >= 1 && xx <= n && yy >=1 && yy <= m && st[xx][yy].x == -1 && ( s[xx][yy] == '.' || s[xx][yy] == 'H') )
                q.push({xx,yy}),st[xx][yy] = t;
        }
    }
}

int main() 
{
    int a,b,c,d;
    cin >> m >> n;
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= m ; j ++ )
        {
            cin >> s[i][j];
            if( s[i][j] == 'K')
                a = i , b = j;
            else if( s[i][j] == 'H')
                c = i, d = j;
        }
    }
//  cout << a << ' ' << b << endl;  
//  cout << c << ' ' << d << endl;
    bfs(a,b);
    PII end(c,d);
    int cnt = 1;
    while(1)
    {
        PII o = st[end.x][end.y];
        end = o;
    //  cout << end.x << ' ' << end.y << endl;

        if( o.x == a && o.y == b )
            break;
        cnt++;

    }
    cout << cnt << endl;
    return 0;
}

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define x first
#define y second
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
typedef pair<int,int> PII;
const int N = 1e3 + 10;
int g[N][N];
PII pre[N][N];
int n;

void bfs(int sx,int sy)
{
    queue<PII> q;
    q.push({sx,sy});
    memset(pre, -1, sizeof pre);
    pre[sx][sy] = {0,0};
    while( q.size() ) 
    {
        PII temp = q.front();
        q.pop();
        for(int i = 0 ; i < 4 ;i ++ )
        {
            int xx = dx[i] + temp.x , yy = dy[i] + temp.y;
            if( xx >= 0 && xx < n && yy >= 0 && yy < n && pre[xx][yy].x == -1 && g[xx][yy] == 0 )
            {
                q.push({xx,yy});
                pre[xx][yy] = temp;
            }
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++ )
        for(int j = 0; j < n ; j++ )
            cin >> g[i][j];

    bfs(n - 1 ,n - 1 );
    PII end(0,0);
    while(1)
    {
        cout << end.x  << ' ' << end.y  << endl;
        if( end.x == n - 1  && end.y == n - 1 ) break;
        end = pre[end.x][end.y];
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1e3 + 10;
bool st[N][N];
int s[N][N];
int n, cnt, res;
int dx[] = {0,-1,-1,-1,0,0,+1,1,1};
int dy[] = {0,-1,0,+1,-1,+1,-1,0,1};
typedef pair<int,int> PII;
void bfs(int a,int b)
{
    bool t = false, tt =false;
    queue<PII> q;
    q.push({a,b});
    st[a][b] = true;
    while( q.size() )
    {
        PII temp = q.front();
        q.pop();
        for(int i = 1; i <= 8; i ++ )
        {
            int xx = temp.x + dx[i], yy = temp.y + dy[i];
            if( xx >= 1 && xx <= n && yy >= 1 && yy  <= n )
            {
                if( s[xx][yy] > s[temp.x][temp.y] )
                    t = true;   //山谷
                else if( s[xx][yy] < s[temp.x][temp.y] )
                    tt =true;   //山峰
            }
        }
        for(int i = 1; i <= 8 ; i++ )
        {
            int xx = temp.x + dx[i] , yy = temp.y + dy[i];
            if( xx >= 1 && xx <= n && yy >= 1 && yy <= n && !st[xx][yy] && s[xx][yy] == s[temp.x][temp.y] )
            {
                q.push({xx,yy});
                st[xx][yy] = true;
            }
        }
    }
    if( t && !tt )  res ++;
    else if( !t && tt ) cnt ++;
    else if(!t && !tt)  res ++ ,cnt ++;

}


int main()
{
    cin >> n ;
    for(int i =1; i <= n; i++ )
        for(int j =1 ; j <= n ; j++ )
            cin >> s[i][j];
    for(int i = 1; i <= n; i++ )
    {
        for(int j = 1; j <= n ; j ++ )
        {
            if( !st[i][j] )
                bfs(i,j);
        }
    }
    cout << cnt << ' ' << res << endl;
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 10;
char s[N];
int main()
{

    while(cin >> s)
    {
        int n = 0;
        for(int i = 0 ; i < strlen(s) ; i ++ )
            n += s[i] - '0';
        if( n == 0 )    break;
        int temp;
        do{
            temp = 0;
            while(n)
            {
                temp += n % 10;
                n /= 10;
            }
            n = temp;
        }while( temp >= 10 );
        cout << temp << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
map<int, int> v;
int main() {
    for (int i = 2; i <= 100 ; i++ )    v[i * i]++;
    int n;
    while (cin >> n ) {
        bool temp = false;
        for (int i = 2; i <= n ; i ++ ) {
            if ( n % i == 0 &&  v[i] != 0  ) {
                temp = true;
                break;
            }
        }
        if (!temp)  cout << "No" << endl;
        else    cout << "Yes" << endl;
    }

    return 0;
}