1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
#define dbg(x) #x << " = " << x << " "
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;

struct rational {
    int p, q;

    void print() { cout << p << "/" << q << "\n"; }
};

bool compare(rational a, rational b) { return 1LL * a.p * b.q < 1LL * b.p * a.q; }

rational normalize(int a, int b) {
    if (a == 0) return {a, abs(b)};

    if (b < 0) {
        a = -a;
        b = -b;
    }

    int g = abs(__gcd(a, b));
    return {a / g, b / g};
}
constexpr int MAXN = 19, MAXL = 10005, MAXL_NATURALIZED = MAXL * MAXN;
bitset<MAXL> blocked[MAXN];
bitset<MAXL_NATURALIZED> wolny[MAXN];
int dostepni[MAXL_NATURALIZED];

int n, L, T;
bool jest_git(int opiekun, int l, int r) {
    for (int i = l; i < r; i++)
        if (!wolny[opiekun][i] || dostepni[i] <= 1) return false;
    return true;
}

bool bergentruckung(int opiekun) {
    if (opiekun == n) return true;
    for (int start = 0; start + T <= L; start++) {
        int mini = MAXN;
        if (jest_git(opiekun, start, start+T)) {
            for (int i = start; i < start+T; i++) {dostepni[i]--; wolny[opiekun][i].flip();}
            if (bergentruckung(opiekun+1)) return true;
            for (int i = start; i < start+T; i++){ dostepni[i]++; wolny[opiekun][i].flip();}
        }
    }

    return false;
}

int q = 1;

void solve(int tc) {
    int L_original;
    cin >> n >> L_original;

    vector good(L_original, false);
    for (int row = 0; row < n; row++) {
        string s;
        cin >> s;
        for (int col = 0; col < L_original; col++) {
            blocked[row][col] = (s[col] == 'X' ? 1 : 0);
            if (!blocked[row][col]) good[col] = true;
        }
    }

    for (auto covered : good) {
        if (!covered) {
            cout << "-1\n";
            return;
        }
    }

    if (n == 1) {
        cout << "0/1\n";
        return;
    }

    vector<rational> ulamki;
    for (int mianownik = 1; mianownik <= n; mianownik++) {
        for (int licznik = 0 + (mianownik > 1); licznik <= mianownik * L_original; licznik++) {
            if (__gcd(mianownik, licznik) == 1) {
                ulamki.push_back(rational{licznik, mianownik});
            }
        }
    }

    sort(ulamki.begin(), ulamki.end(),
         [](const auto &lhs, const auto &rhs) { return compare(lhs, rhs); });

    auto check = [&](rational mid) {
        T = mid.p;
        L = L_original * mid.q;
        for (int c = 0; c < L; c++) dostepni[c] = 0;

        for (int row = 0; row < n; row++) {
            int col_expanded = 0;
            for (int col = 0; col < L_original; col++) {
                for (int rep = 0; rep < mid.q; rep++) {
                    if (!blocked[row][col]) dostepni[col_expanded]++;
                    wolny[row][col_expanded] = !blocked[row][col];
                    col_expanded++;
                }
            }
        }

        bool ret = bergentruckung(0);
        // cerr << dbg(mid.p) << dbg(mid.q) << dbg(ret) << endl;
        return ret;
    };

    int lo = 0, hi = ulamki.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (check(ulamki[mid]))
            lo = mid;
        else
            hi = mid - 1;
    }
    
    ulamki[lo].print();
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    int q = 1;
    cin >> q;
    for (int tc = 1; tc <= q; tc++) {
        if (tc % 1000 == 0) cerr << q - tc << endl;
        solve(tc);
    }
}