Facebook Hacker Cup: Problem B: Xs and Os

/*https://www.facebook.com/codingcompetitions/hacker-cup/2021/qualification-round/problems/B*/
#include<bits/stdc++.h>
using  namespace  std;

#define endl         "\n"
#define ll           long long
#define PI           acos(-1.0)
#define GCD(a,b)     __gcd(a , b)
#define LCM(a,b)     ((a/__gcd(a,b))*b)
#define READ(f)      freopen(f,"r",stdin)
#define WRITE(f)     freopen(f,"w",stdout)
#define test         cout<<"\n*************\n"
#define mem(arr,val) memset(arr,val,sizeof(arr))
#define precise(c)   fixed(cout);cout<<setprecision(c)
#define valid(x,y)   (x>=0 && x<row && y>=0 && y<column)
#define fast         ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)


char arr[100][100];
char arrcount[100][100];

ll horizontal(ll x, ll n, bool minimumfound,ll minimum_element, bool one){

    if(one){

        bool flag = true;
        for(ll i=0;i<n;i++){
            if(arrcount[x][i] == '.' && minimum_element){
                minimum_element--;
                arrcount[x][i] = '#';
            } else if(arrcount[x][i]=='#' || arrcount[x][i] == 'O' || (minimum_element==0 && arrcount[x][i]=='.')){
                flag = false;
            }
        }

        if(flag){
            return 1;
        } else{
            for(ll i=0;i<n;i++){
                if(arrcount[x][i] == '#'){
                    arrcount[x][i] = '.';
                }
            }
            return 0;
        }


    } else if(!minimumfound){
        ll numx = 0;
        bool flag = true;
        for(ll i=0;i<n;i++){
            if(arr[x][i] == '.' || arr[x][i] == '*'){
                arr[x][i] = '*';
                numx++;
            } else if(arr[x][i] == 'O'){
                flag = false;
            }
        }

        if(flag){
            return numx;
        } else{
            return 100000;
        }
    } else{


        bool flag = true;
        for(ll i=0;i<n;i++){
            if(arrcount[x][i] == '.' && minimum_element){
                minimum_element--;

            } else if(arrcount[x][i]=='#' || arrcount[x][i] == 'O' || (minimum_element==0 && arrcount[x][i]=='.')){
                flag = false;
            }
        }

        if(flag){

            return 1;
        } else{
            return 0;
        }


    }
}

ll vertical(ll x, ll n, bool minimumfound,ll minimum_element, bool one){

    if(one){

        bool flag = true;
        for(ll i=0;i<n;i++){
            if(arrcount[i][x] == '.' && minimum_element){
                minimum_element--;
                arrcount[i][x] = '#';
            } else if(arrcount[i][x]=='#' || arrcount[i][x] == 'O' || (minimum_element==0 && arrcount[i][x]=='.')){
                flag = false;
            }
        }

        if(flag){

            return 1;
        } else{
            for(ll i=0;i<n;i++){
                if(arrcount[i][x] == '#'){
                    arrcount[i][x] = '.';
                }
            }
            return 0;
        }

    } else if(!minimumfound) {
        ll numx = 0;
        bool flag = true;
        for (ll i = 0; i < n; i++) {
            if (arr[i][x] == '.' || arr[i][x] == '*') {
                arr[i][x] = '*';
                numx++;
            } else if (arr[i][x] == 'O') {
                flag = false;
            }
        }

        if (flag) {
            return numx;
        } else {
            return 100000;
        }
    } else{

        bool flag = true;

        for(ll i=0;i<n;i++){
            if(arrcount[i][x] == '.' && minimum_element){
                minimum_element--;
            } else if(arrcount[i][x]=='#' || arrcount[i][x] == 'O' || (minimum_element==0 && arrcount[i][x]=='.')){
                flag = false;
            }
        }

        if(flag){

            return 1;
        } else{
            return 0;
        }

    }
}


int main(){


    READ("input.txt");
    WRITE("out.txt");

    ll t, con = 1;
    cin>>t;

    while(t--){

        ll n;
        cin>>n;
        bool minimumfound = false;

        for(ll i=0;i<n;i++){
            for(ll j=0;j<n;j++){
                cin>>arr[i][j];
                arrcount[i][j] = arr[i][j];
            }
        }

        vector<ll> x;
        bool one = false;

        ll minimum_element = 0;
        for(ll i=0;i<n;i++){
            ll numx = 0;
            numx = horizontal(i, n,minimumfound,minimum_element,one);
            x.push_back(numx);
        }

        for(ll i=0;i<n;i++){
            ll numx = 0;
            numx= vertical(i, n, minimumfound,minimum_element,one);
            x.push_back(numx);
        }


        minimum_element = *min_element(x.begin(),x.end());
        ll count = 0;

        minimumfound = true;


        if(minimum_element==1){
            one = true;
        }

        for(ll i=0;i<n;i++){
            count = count + horizontal(i, n,minimumfound,minimum_element,one);
        }

        for(ll i=0;i<n;i++){
            count = count + vertical(i, n, minimumfound,minimum_element,one);
        }


        if(minimum_element==100000){
            cout << "Case #" << con << ": Impossible"<< endl;
        } else{
            cout << "Case #" << con << ": " <<minimum_element<<" "<<count<< endl;
        }


        con++;
    }

    return 0;
}