#include <fstream>
#include <vector>
#include <random>
#include <chrono>

#include <iostream>

using namespace std;

int32_t rand_max = 4549;
mt19937 mt_generator(static_cast<unsigned>(time(nullptr)));
uniform_int_distribution<> uniformIntDistribution(1, rand_max);

class DanceTriples {
    void init_tutte_matrix() {
        tutte.clear();
        tutte.resize(2 * males + females);

        for (int32_t i = 0; i < 2 * males + females; ++i) {
            tutte[i].resize(2 * males + females, 0);
        }

        for (int32_t i = 0; i < links.size(); ++i) {
            int32_t from = links[i].first;
            int32_t to = links[i].second;
            int32_t rand_v = uniformIntDistribution(mt_generator);

            tutte[from][to] = rand_v;
            tutte[to][from] = rand_max - rand_v;
        }

//        for (size_t i = 0; i < 2 * males + females; i++) {
//            for (size_t j = 0; j < 2 * males + females; j++) {
//                cout << tutte[i][j] << "\t";
//            }
//            cout << "\n";
//        }
    }

    int32_t get_invert_coeff(uint32_t x, uint32_t p) {
        uint32_t p_dcr = p - 2;
        long long k = 1;
        long long j = x;

        while (p_dcr > static_cast<unsigned>(0)) {
            if ((p_dcr & static_cast<unsigned>(1)) > 0) {
                k = (k * j) % p;
            }

            j = (j * j) % p;
            p_dcr = p_dcr >> static_cast<unsigned>(1);
        }

        return static_cast<int32_t>(k % p);
    }

    int32_t get_tutte_rank_v2() {
        int32_t size = 2 * males + females;
        int32_t rank = 0, row = 0, col = 0;

        while (max(row, col) < size) {
            int32_t swap_index = 0;
            bool index_set = false;
            for (int32_t j = row; j < size; ++j) {
                if (tutte[j][col] != 0) {
                    ++rank;
                    swap_index = j;
                    index_set = true;
                    if (row != swap_index) {
                        swap(tutte[row], tutte[swap_index]);
                    }
                    break;
                }
            }
            if (!index_set) {
                ++col;
            } else {
                for (int32_t i = row + 1; i < size; ++i) {
                    int32_t factor = (tutte[i][col] * get_invert_coeff(tutte[row][col], rand_max)) % rand_max;
                    for (int32_t j = col; j < size; ++j) {
                        if (j == col) {
                            tutte[i][j] = 0;
                        } else {
                            tutte[i][j] = ((rand_max - ((tutte[row][j] * factor) % rand_max)) + tutte[i][j]) % rand_max;
                        }
                    }
                }
                ++col;
                ++row;
            }
        }
        return rank;
    }

    int32_t males = 0;
    int32_t females = 0;
    vector<pair<int32_t, int32_t>> links;
    vector<vector<int32_t>> tutte;

public:
    DanceTriples(istream &input) {
        input >> males >> females;

        // first  males located, than males dups, than females
        for (int32_t i = 0; i < males; i += 1) {
            links.push_back(make_pair(i, i + males));
        }

        for (int32_t i = 0; i < males; ++i) {
            string linkeage;
            input >> linkeage;

            for (int32_t j = 0; j < females; ++j) {
                if (linkeage[j] == '1') {
                    links.push_back(make_pair(i, 2 * males + j));
                    links.push_back(make_pair(i + males, 2 * males + j));
                }
            }
        }
    }

    int32_t get_triples_num() {
        int32_t max_checks = 5;
        int32_t max_triples = 0;

        for (int i = 0; i < max_checks; ++i) {
            init_tutte_matrix();
            int32_t rank_v2 = get_tutte_rank_v2();
            int32_t triples = (rank_v2 / 2) - males;
            max_triples = max(triples, max_triples);
        }

        return max_triples;
    }
};


int main() {
    ifstream input_stream;
    input_stream.open("triples.in");

    ofstream output_stream;
    output_stream.open("triples.out");

    int32_t dance_parties = 0;
    input_stream >> dance_parties;

    for (int32_t i = 0; i < dance_parties; ++i) {
        DanceTriples dance_party(input_stream);
        int32_t triples = dance_party.get_triples_num();
        output_stream << triples << '\n';
    }

    input_stream.close();
    output_stream.close();

    return 0;
}