using namespace std;
using ll = long long;
using vi = vector<int>;
int const NMAX = 10;
int n, m, diff[NMAX];
string a[NMAX], ans;
bool backtrack(int i)
{
    if (i == m)
        return true;
    vector<bool> visited(26, false);
    for (int j = 0; j < n; ++j)
    {
        char c = a[j][i];
        bool ok = true;
        if (visited[c - 'a'])
            continue;
        visited[c - 'a'] = true;
        for (int k = 0; k < n; ++k)
        {
            diff[k] += (a[j][i] != a[k][i]);
            if (diff[k] > 1)
                ok = false;
        }
        ans[i] = c;
        if (ok and backtrack(i + 1))
            return true;
        ans[i] = ' ';
        for (int k = 0; k < n; ++k)
            diff[k] -= (a[j][i] != a[k][i]);
    }
    return false;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        ans.resize(m, ' ');
        fill(diff, diff + NMAX, 0);
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        if (backtrack(0))
            cout << ans << endl;
        else
            cout << -1 << endl;
    }
    return 0;
}

using namespace std;
const int NMAX = 50;
int n;
bool bomb[NMAX][NMAX];
bool valid(int i, int j)
{
    if (i == n - 1 or j == n - 1)
        return true;
    return bomb[i + 1][j] or bomb[i][j + 1];
}
bool board_possible(void)
{
    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = n - 1; j >= 0; --j)
        {
            if (bomb[i][j] and not valid(i, j))
                return false;
        }
    }
    return true;
}
int main(void)
{
    char c;
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                cin >> c;
                bomb[i][j] = c == '1';
            }
        }
        cout << (board_possible() ? "YES" : "NO") << endl;
    }
    return 0;
}

using namespace std;
int solve(int n, int k)
{
    int ans = INT_MAX, d1, d2;
    for (int i = 1, len = (int)sqrt(n); i <= len; ++i)
    {
        if (n % i == 0)
        {
            d1 = i;
            d2 = n / i;
            if (d2 <= k)
                ans = min(ans, d1);
            if (d1 <= k)
                ans = min(ans, d2);
        }
    }
    return ans;
}
int main(void)
{
    int t, n, k;
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

using namespace std;
const int NMAX = 50;
int n, a[NMAX];
bool solve(void)
{
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        if (a[i] % 2 == 0)
            cnt += 1;
    if (cnt % 2 == 0)
        return true;
    sort(a, a + n);
    for (int i = 1; i < n; ++i)
        if (a[i] - a[i - 1] == 1)
            return true;
    return false;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        cout << (solve() ? "YES" : "NO") << endl;
    }
}

using namespace std;
const int NMAX = 50;
int n, s[NMAX];
int solve(void)
{
    int ans = INT_MAX;
    sort(s, s + n);
    for (int i = 1; i < n; ++i)
        ans = min(ans, s[i] - s[i - 1]);
    return ans;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> s[i];
        cout << solve() << endl;
    }
    return 0;
}

using namespace std;
int main(void)
{
    int t, a, b, ans;
    cin >> t;
    while (t--)
    {
        cin >> a >> b;
        if (a > b)
            swap(a, b);
        if (2 * a > b)
            ans = 2 * a * 2 * a;
        else
            ans = b * b;
        cout << ans << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
struct point
{
    ll x, y;
    int id;
    bool operator<(const point &o) const { return id < o.id; }
    point operator-(const point &o) const { return {x - o.x, y - o.y, id}; }
};
ll dot_product(point a, point b) { return a.x * b.x + a.y * b.y; }
bool orthogonal(point a, point b, point c)
{
    return dot_product(b - a, b - c) == 0;
}
ll sq(ll x) { return x * x; }
ll d2(point a, point b) { return sq(a.x - b.x) + sq(a.y - b.y); }
bool rectangle(point a, point b, point c, point d)
{
    return orthogonal(a, b, c) and orthogonal(b, c, d) and
           orthogonal(c, d, a) and orthogonal(d, a, b);
}
bool square(point a, point b, point c, point d)
{
    return rectangle(a, b, c, d) and d2(a, b) == d2(b, c);
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    point a[8];
    for (int i = 0; i < 8; i++)
    {
        cin >> a[i].x >> a[i].y;
        a[i].id = i + 1;
    }
    do
    {
        if (square(a[0], a[1], a[2], a[3]) and
            rectangle(a[4], a[5], a[6], a[7]))
        {
            cout << "YES" << endl;
            for (int i = 0; i < 4; i++)
                cout << a[i].id << ' ';
            cout << endl;
            for (int i = 4; i < 8; i++)
                cout << a[i].id << ' ';
            cout << endl;
            return 0;
        }
    } while (next_permutation(a, a + 8));
    cout << "NO" << endl;
}

using namespace std;
using ll = long long;
int main(void)
{
    int t, n, m;
    ll ans;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        ans = n * (m / 2);
        if (m % 2 == 1)
        {
            if (n % 2 == 0)
                ans += n / 2;
            else
                ans += n / 2 + 1;
        }
        cout << ans << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 1e6 + 11;
int n, k, a[NMAX];
int solve(void)
{
    int sum = accumulate(a, a + n, 0);
    int ans = sum;
    for (int i = 0; i < k; ++i)
    {
        vi dp(n / k + 1, 0);
        vi acc(n / k + 1, 0);
        int m = 0;
        for (int j = i; j < n; j += k, ++m)
        {
            dp[m] = (a[j] != 1);
            if (m > 0)
                dp[m] += min(dp[m - 1], acc[m - 1]);
            acc[m] = a[j] + (m == 0 ? 0 : acc[m - 1]);
        }
        for (int j = 0; j < m; ++j)
            ans = min(ans, dp[j] + sum - acc[j]);
    }
    return ans;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> n >> k >> s;
        for (int i = 0; i < n; ++i)
            a[i] = s[i] - '0';
        cout << solve() << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 1e5 + 11;
int n, s[NMAX];
int solve(void)
{
    vi dp(n + 1, 1);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j * i <= n; ++j)
            if (s[i] < s[i * j])
                dp[i * j] = max(dp[i * j], dp[i] + 1);
    }
    return *max_element(dp.begin(), dp.end());
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> s[i];
        cout << solve() << endl;
    }
    return 0;
}