#include <iostream>
#include <unordered_set>

using namespace std;

const int N = 7;

int n, m, k;
int num[N][N];

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

unordered_set<int> dfs(int x, int y, int c)
{
    unordered_set<int> S;

    int val = num[x][y];
    for (int i = 0; i < c - 1; ++i) val *= 10;

    if (c == 1) S.insert(val);
    else for (int i = 0; i < 4; ++i)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        auto s = dfs(a, b, c - 1);
        for (auto &t : s)
            S.insert(val + t);
    }

    return S;
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> num[i][j];

    unordered_set<int> S;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            auto s = dfs(i, j, k + 1);
            for (auto &x : s)
                S.insert(x);
        }

    cout << S.size() << endl;

    return 0;
}

#include <iostream>
#include <unordered_set>

using namespace std;

const int N = 7;

int n, m, k;
int num[N][N];
unordered_set<int> S;

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

void dfs(int x, int y, int c, int val)
{
    if (c == k) S.insert(val);
    else for (int i = 0; i < 4; ++i)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        dfs(a, b, c + 1, val * 10 + num[a][b]);
    }
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> num[i][j];

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            dfs(i, j, 0, num[i][j]);

    cout << S.size() << endl;

    return 0;
}

#include <iostream>
#include <queue>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n;
char g[N][N];
bool st[N][N]; 

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

bool bfs(PII start)
{
    queue<PII> q;
    q.push(start);
    st[start.x][start.y] = true;

    bool tag = true; //该岛会被淹没
    while (q.size())
    {
        auto &t = q.front();
        q.pop();

        int x = t.x, y = t.y;
        bool flag = true;  //该礁不会被淹没
        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i], b = y + dy[i];

            if (g[a][b] == '.') flag = false;
            else if (!st[a][b]) q.push({a, b}), st[a][b] = true;
        }
        if (flag) tag = false;
    }
    return tag;
}

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

    int res = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (g[i][j] == '#' && !st[i][j])
                if(bfs({i, j})) res++;

    cout << res << endl;

    return 0;
}

#include <iostream>
#include <unordered_map>
#include <queue>

using namespace std;

string dest = "12345678x";

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

int bfs(string str)
{
    queue<string> q;
    unordered_map<string, int> dist;

    dist[str] = 0;
    q.push(str);

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        int idx = t.find("x");

        if (t == dest) return dist[t];

        int x = idx / 3, y = idx % 3;

        for (int i = 0; i < 4; ++i)
        {
            string mov(t);
            int a = x + dx[i], b = y + dy[i];

            if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;

            swap(mov[idx], mov[a * 3 + b]);
            if (!dist.count(mov))
            {
                q.push(mov);
                dist[mov] = dist[t] + 1;
            }
        }
    }
    return -1;
}

int main()
{
    string str;
    for (int i = 0; i < 9; ++i)
    {
        string t;
        cin >> t;
        str += t;
    }

    cout << bfs(str) << endl;

    return 0;
}

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N], dist[N][N];
PII q[N * N];

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

int bfs(int a, int b)
{
    memset(dist, -1, sizeof dist);
    dist[a][b] = 0;

    int hh = 0, tt = 0;
    q[0] = {a, b};

    while (hh <= tt)
    {
        auto &t = q[hh++];
        int x = t.x, y = t.y;
        if (x == n && y == m) return dist[x][y];

        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a <= 0 || a > n || b <= 0 || b > m) continue;
            if (dist[a][b] != -1 || g[a][b] == 1) continue;
            dist[a][b] = dist[x][y] + 1;
            q[++tt] = {a, b};
        }
    }
    return -1;
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        for (int j = 1 ; j <= m; ++j)
            scanf("%d", &g[i][j]);

    cout << bfs(1, 1) << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 1010, L = 8;

int n, l, m;
int q[L * N];
vector<int> list[N];
bool st[N];

int bfs(int start)
{
    memset(st, 0, sizeof st);

    int hh = 0, tt = 0;
    q[0] = start;
    st[start] = true;

    int res = 0;
    for (int i = 0; i < l; i ++ )
    {
        int sz = tt - hh + 1;
        while (sz--)
        {
            int t = q[hh++];
            for (auto &x : list[t])
            {
                if (!st[x])
                {
                    q[++tt] = x;
                    st[x] = true;
                    res ++ ;
                }
            }
        }
    }

    return res;
}

int main()
{
    cin >> n >> l;

    for (int i = 1; i <= n; ++i)
    {
        int cnt;
        scanf("%d", &cnt);
        for (int j = 0; j < cnt; ++j)
        {
            int id;
            scanf("%d", &id);
            list[id].push_back(i);
        }
    }

    cin >> m;
    while (m--)
    {
        int id;
        scanf("%d", &id);
        printf("%d\n", bfs(id));
    }

    return 0;
}

#include <iostream>

using namespace std;

const int N = 100010, M = 3100010;

int n, m;
int eor[N];
int son[M][2], cnt[N], idx, contain[M];

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; --i)
    {
        int t = x >> i & 1;
        if (!son[p][t]) son[p][t] = ++idx;
        p = son[p][t];
        contain[p]++;
    }
    cnt[p]++;
}

void erase(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; --i)
    {
        int t = x >> i & 1;
        if (!son[p][t]) return;
        int u = son[p][t];

        contain[u]--;
        if (contain[u] == 0) 
        {
            son[p][t] = 0;
            return;
        }
        p = son[p][t];
    }
}

//
int get(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; --i)
    {
        int t = x >> i & 1;
        if (son[p][!t]) p = son[p][!t], res = res * 2 + !t;
        else if (son[p][t]) p = son[p][t], res = res * 2 + t;
    }
    return res ^ x;
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) scanf("%d", &eor[i]), eor[i] ^= eor[i - 1];

    int res = 0;
    for (int i = 0; i <= n; ++i)
    {
        if (i - m - 1 >= 0) erase(eor[i - m - 1]);
        res = max(res, get(eor[i]));
        insert(eor[i]);
    }
    cout << res << endl;

    return 0;
}

#include <iostream>

using namespace std;

const int N = 100010, M = 3100010;

int a[N];
int son[M][2], idx;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; --i)
    {
        int t = x >> i & 1;
        if (!son[p][t]) son[p][t] = ++idx;
        p = son[p][t];
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; --i)
    {
        int t = x >> i & 1;
        if (son[p][!t]) 
        {
            p = son[p][!t];
            res = res * 2 + !t;
        }
        else 
        {
            p = son[p][t];
            res = res * 2 + t;
        }
    }
    return res;
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) 
    {
        scanf("%d", &a[i]);
        insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = query(a[i]);
        res = max(res, t ^ a[i]);
    }

    cout << res << endl;

    return 0;
}

#include <iostream>

using namespace std;

const int N = 100010;

char str[N];
int son[N][26], cnt[N], idx;

void insert(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; ++i)
    {
        int t = str[i] - 'a';
        if (!son[p][t]) son[p][t] = ++idx;
        p = son[p][t];
    }
    cnt[p]++;
}

int query(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; ++i)
    {
        int t = str[i] - 'a';
        if (!son[p][t]) return 0;
        p = son[p][t];
    }
    return cnt[p];
}

int main()
{
    int n;
    cin >> n;

    while (n--)
    {
        char op[2];
        scanf("%s%s", op, str);

        if (op[0] == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;

typedef long long LL;

struct Point
{
    LL x, y;
};

Point get(int n, LL id)
{
    if (n == 0) return {0, 0};

    LL block = 1ll << 2 * n - 2, len = 1ll << n - 1;

    auto p = get(n - 1, id % block);
    int x = p.x, y = p.y, z = id / block;

    if (z == 0) return {y, x};
    else if (z == 1) return {x, y + len};
    else if (z == 2) return {x + len, y + len};
    else return {2 * len - 1 - y, len - 1 - x};
}

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        LL n, a, b;
        scanf("%lld%lld%lld", &n, &a, &b);

        Point pa = get(n, a - 1), pb = get(n, b - 1);
        double dx = pa.x - pb.x, dy = pa.y - pb.y;
        printf("%.0lf\n", sqrt(dx * dx + dy * dy) * 10);
    }

    return 0;
}