#include "stdafx.h"

#include <memory.h>

#include <iostream>


using namespace std;


#define WIDTH   (6 + 2)

#define HEIGHT  (5 + 2)

#define K_COUNT (5)


#define UP      (pos - WIDTH)

#define DOWN    (pos + WIDTH)

#define LEFT    (pos - 1)

#define RIGHT   (pos + 1)


const char lines[] = { 5, 5, 2, 1, 5, 5, 4, 3, 3, 1, 6, 6, 4, 2, 6, 6, };


typedef struct ENTRY

{

    char goal;

    int pos;

    ENTRY(char g, int x, int y) { goal = g, pos = y * WIDTH + x; }

    ENTRY() {}

} ENTRY;


int     c, r, k;

char    map[WIDTH * HEIGHT];

int     symbols[256];

ENTRY   entry[K_COUNT];

int     answer;


void print_map()

{

    for (int y = 1; y <= r; ++y)

    {

        for (int x = 1; x <= c; ++x)

            cout << map[y * WIDTH + x];

        cout << endl;

    }

    cout << endl;

}


void build_map()

{

    memset(map, 0, sizeof(map));

    memset(symbols, 0, sizeof(symbols));

    int count = 0;

    for (int y = 1; y <= r; ++y)

    {

        for (int x = 1; x <= c; ++x)

        {

            char s;

            cin >> s;

            if (s == '*')

                map[y * WIDTH + x] = s;

            else if (symbols[s])

                map[y * WIDTH + x] = s + 32;

            else

                map[y * WIDTH + x] = s,

                entry[count++] = ENTRY(s + 32, x, y);

symbols[s] = 1;

        }

    }

}


void run(int i, int pos, int step);


inline void trace(char dir, int old, int i, int now, int step)

{

    char back = map[old];

    if (map[old] < '*')

        map[old] = lines[map[old] << 2 | dir];

    if (map[now] == '*')

    {

        map[now] = dir;

        run(i, now, step + 1);

        map[now] = '*';

    }

    else if (map[now] == entry[i].goal)

    {

        if (i + 1 < k)

            run(i + 1, entry[i + 1].pos, step);

        else if (step == c * r - k * 2)

        {

            answer++;

            print_map();

        }

    }

    map[old] = back;

}


void run(int i, int pos, int step)

{

    trace(0, pos, i,    UP, step);

    trace(1, pos, i,  DOWN, step);

    trace(2, pos, i,  LEFT, step);

    trace(3, pos, i, RIGHT, step);

}


int main()

{

    int t;

    cin >> t;

    while (t--)

    {

        answer = 0;

        cin >> r >> c >> k;

        build_map();

        print_map();

        run(0, entry[0].pos, 0);

        cout << "answer : " << answer << endl;

        cout << "----------" << endl;

    }

    return 0;

}


마지막 것만.