Kim likes to play Tic-Tac-Toe.

Given a current state, and now Kim is going to take his next move. Please tell Kim if he can win the game in next 2 moves if both player are clever enough.

Here “next 2 moves” means Kim’s 2 move. (Kim move,opponent move, Kim move, stop).

Game rules:

Tic-tac-toe (also known as noughts and crosses or Xs and Os) is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game.

First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: Each test case contains three lines, each line three string(“o” or “x” or “.”)(All lower case letters.)

x means here is a x

o means here is a o

. means here is a blank place.

Next line a string (“o” or “x”) means Kim is (“o” or “x”) and he is going to take his next move.

For each test case:

If Kim can win in 2 steps, output “Kim win!”

Otherwise output “Cannot win!”

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <bitset>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <algorithm>

#define ls (r<<1)

#define rs (r<<1|1)

#define debug(a) cout << #a << " " << a << endl

using namespace std;

typedef long long ll;

const ll maxn = 10;

const double eps = 1e-8;

const ll mod = 1e9 + 7;

const ll inf = 1e9;

const double pi = acos(-1.0);

char mp[maxn][maxn];

bool check( char c ) {

    if(mp[1][1]==c&&mp[1][1]==mp[1][2]&&mp[1][1]==mp[1][3]) return true;

    if(mp[2][1]==c&&mp[2][1]==mp[2][2]&&mp[2][1]==mp[2][3]) return true;

    if(mp[3][1]==c&&mp[3][1]==mp[3][2]&&mp[3][1]==mp[3][3]) return true;

    if(mp[1][1]==c&&mp[1][1]==mp[2][1]&&mp[1][1]==mp[3][1]) return true;

    if(mp[1][2]==c&&mp[1][2]==mp[2][2]&&mp[1][2]==mp[3][2]) return true;

    if(mp[1][3]==c&&mp[1][3]==mp[2][3]&&mp[1][3]==mp[3][3]) return true;

    if(mp[1][1]==c&&mp[1][1]==mp[2][2]&&mp[1][1]==mp[3][3]) return true;

    if(mp[1][3]==c&&mp[1][3]==mp[2][2]&&mp[1][3]==mp[3][1]) return true;

    return false;

}

bool ok( char c ) {

    if( check(c) ) { //是否构成三子相连

        return true;

    }

    ll cnt = 0;

    //是否有两个地方可以再下一颗棋子构成三子相连

    for( ll i = 1; i <= 3; i ++ ) {

        for( ll j = 1; j <= 3; j ++ ) {

            if( mp[i][j] == '.' ) {

                mp[i][j] = c;

                if( check(c) ) {

                    cnt ++;

                }

                mp[i][j] = '.';

            }

        }

    }

    if( cnt >= 2 ) {

        return true;

    }

    return false;

}

int main() {

    ll T;

    cin >> T;

    while( T -- ) {

        for( ll i = 1; i <= 3; i ++ ) {

            for( ll j = 1; j <= 3; j ++ ) {

                cin >> mp[i][j];

            }

        }

        char c1, c2;

        cin >> c1;

        if( c1 == 'x' ) {

            c2 = 'o';

        } else {

            c2 = 'x';

        }

        bool flag = false;

        for( ll i = 1; i <= 3; i ++ ) {

            for( ll j = 1; j <= 3; j ++ ) {

                if( mp[i][j] == '.' ) {

                    mp[i][j] = c1;

                    if( !ok(c2) && ok(c1) ) {

                        flag = true;

                    }

                    mp[i][j] = '.';

                }

            }

        }

        if( flag ) {

            cout << "Kim win!" << endl;

        } else {

            cout << "Cannot win!" << endl;

        }

    }

    return 0;

}