/**
 * Author: Aravind Nujella
 * ${TM_FILENAME} : ${CURRENT_DAY_NAME_SHORT},
 * ${CURRENT_DATE}-${CURRENT_MONTH}-${CURRENT_YEAR}
 */
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n)       for (int i = 0; i < (n); ++i)
#define forw(i, l, r)   for (int i = (l); i < (r); ++i)
#define forall(i, l, r) for (int i = (l); i <= (r); ++i)
#define rev(i, n)       for (int i = (n)-1; i >= 0; --i)
#define backw(i, l, r)  for (int i = (r)-1; i >= (l); --i)
#define revall(i, l, r) for (int i = (r); i >= (l); --i)
#define all(x)          (x).begin(), (x).end()
#define contains(x, i)  (x.find(i) != x.end())
#define fic(i, c)       for (auto &i : c)
#define fpic(a, b, c)   for (auto &[a, b] : c)
#define iter(it, x)     for (auto it = x.begin(); it != x.end(); ++it)
#define mp              make_pair
#define _0              first
#define _1              second
#define tos             to_string
#define pct             __builtin_popcount
#define ctz             __builtin_ctz
#define clz             __builtin_clz
#define SOMET           template <typename T>
#define TARGS           template <typename T, typename... Args>
#define TAP             T, Args...
#define ARGS            template <typename... Args>
#define EXP             Args...
#define KV              template <typename K, typename V>
#define KVT             template <typename K, typename V, typename T>
#define tget(tup, i)    get<i>(tup)
#define inf             (1 << 20)
#define mun             begin()
#define chi             end()
using lld = long long;
using ulld = unsigned long long;
using uint = unsigned int;
using vi = vector<int>;
using mii = map<int, int>;
using si = set<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvp = vector<vpii>;
using vvi = vector<vi>;
using vlld = vector<lld>;
using vb = vector<bool>;
SOMET using couple = array<T, 2>;
SOMET using triple = array<T, 3>;
SOMET using quad = array<T, 4>;
template <size_t n> using intarr = array<int, n>;
using ci = couple<int>;
using ti = triple<int>;
using qi = quad<int>;
using vci = vector<ci>;
using vti = vector<ti>;
using vqi = vector<qi>;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T>
// using ord_set =
//     tree<T, null_type, less<T>, rb_tree_tag,
//     tree_order_statistics_node_update>;

// clang-format off


int operator~(string s) { return (int)s.size(); }
char operator^(string s, int v) { return s[~s - 1 - v]; }
char operator-(string &s) { return s[~s - 1]; }

TARGS void operator+=(vector<TAP> &s, T v) { s.push_back(v); }
TARGS T operator-(vector<TAP> &s) { return s[~s - 1]; }
TARGS T operator^(vector<TAP> &s, int v) { return s[~s - 1 - v]; }
TARGS T operator--(vector<TAP>& s) { auto k = -s; s.pop_back(); return k; }
TARGS int operator~(const vector<TAP>& s) { return (int)s.size(); }

template<typename T, size_t n> size_t operator~(const array<T, n>& s) { return (int)s.size(); }

TARGS void operator+=(stack<TAP>& s, T v) { s.push(v); }
TARGS T operator-(stack<TAP>& s) { return s.top(); }
TARGS T operator--(stack<TAP>& s) { auto k = -s; s.pop(); return k; }
TARGS int operator~(const stack<TAP>& s) { return (int)s.size(); }

TARGS void operator+=(queue<TAP>& s, T v) { s.push(v); }
TARGS T operator-(queue<TAP>& s) { return s.front(); }
TARGS T operator--(queue<TAP>& s) { auto k = -s; s.pop(); return k; }
TARGS int operator~(const queue<TAP>& s) { return (int)s.size(); }


TARGS void operator+=(priority_queue<TAP>& s, T v) { s.push(v); }
TARGS T operator-(priority_queue<TAP>& s) { return s.top(); }
TARGS T operator--(priority_queue<TAP>& s) { auto k = -s; s.pop(); return k; }
TARGS int operator~(const priority_queue<TAP>& s) { return (int)s.size(); }

TARGS void operator+=(set<TAP>& s, T v) { s.insert(v); }
TARGS void operator-=(set<TAP>& s, T v) { s.erase(v); }
TARGS bool operator<(T v, set<TAP>& s) { return s.find(v) != s.end(); }
TARGS bool operator>(T v, set<TAP>& s) { return s.find(v) == s.end(); }
TARGS int operator~(const set<TAP>& s) { return (int)s.size(); }

KV void operator+=(map<K, V>& s, pair<K, V> v) { s.insert(v); }
KV void operator-=(map<K, V>& s, K v) { s.erase(v); }
TARGS bool operator<(T v, const map<TAP>& s) { return s.find(v) != s.end(); }
TARGS bool operator>(T v, const map<TAP>& s) { return s.find(v) == s.end(); }
TARGS int operator~(const map<TAP>& s) { return (int)s.size(); }

SOMET void pvec(const vector<T>& v) {
    stringstream i_tos, v_tos;
    i_tos << " i "; v_tos << "arr";
    rep(i, ~v) {
        int w = max({~tos(v[i]), ~tos(i), (size_t)3});
        i_tos << setw(w) << tos(i) << " ";
        v_tos << setw(w) << tos(v[i]) << " ";
    }
    cout << "i :" << i_tos.str() << "\na :" << v_tos.str() << "\n";
}

SOMET void p2vec(vector<vector<T>>& v)
{ rep(i, ~v) { cout << "Row: " << i << "\n"; pvec(v[i]); } }
SOMET void pmat(vector<vector<T>>& v) {
    int h = ~v, w = ~v[0], z = 3;
    cout << "\n" << setw(z) << "+" << " ";
    rep(j, w) cout << setw(z) << j << " \n"[j == (w - 1)];
    rep(i, h) {
        cout << setw(z) << i << " ";
        rep(j, w) cout << setw(z) << v[i][j] << " \n"[j == (w - 1)];
    }
    cout << "\n";
}

SOMET void read(vector<T>& v);
KV void read(pair<K, V>& p);
KV void read(pair<K, V>& p) { read(p.f, p.s); }
SOMET void read(vector<T>& v) { rep(i, ~v) cin >> v[i]; }
SOMET void read(T& x) { cin >> x; }
TARGS void read(T& head, Args&... rest) { read(head); read(rest...); }

#define reint(n)                int n; read(n);
#define rechar(c)               char c; read(c);
#define restring(s)             string s; read(s);
#define re2int(a, b)            int a, b; read(a, b);
#define re3int(a, b, c)         int a, b, c; read(a, b, c);
#define re4int(a, b, c, d)      int a, b, c, d; read(a, b, c, d);
#define ren_vec(n, x)           int n; read(n); vi x(n); read(x);
#define revec(n, x)             vi x(n); read(x);
// #define retp(tp, x)            tp x; read(x);
// #define retp2(tp, x, y)        tp x, y; read(x, y);
// #define retp3(tp, x, y, z)     tp x, y, z; read(x, y, z);
// #define retp4(tp, x, y, z, w)  tp x, y, z, w; read(x, y, z, w);
// #define retpn_vec(tp, n, x)    int n; read(n); vector<tp> x; read(x);

const char* __sep__[2] = {", ", " "};
ARGS ostream& operator<<(ostream& os, const vector<EXP>& v) {
    os << "[ ";
    rep(i, ~v) {os << v[i] << __sep__[i + 1 == ~v];}
    return os << "]";
}
template<typename T, size_t n>
ostream& operator<<(ostream& os, const array<T, n>& v) {
    os << "[ ";
    rep(i, ~v) {os << v[i] << ", "[i + 1 == ~v];}
    return os << "]";
}
ARGS ostream& operator<<(ostream& os, const set<EXP>& v) {
    os << "{ ";
    iter(it, v) os << *it << __sep__[next(it) == v.end()];
    return os << "}";
}
KV ostream& operator<<(ostream& os, const map<K, V>& v) {
    os << "{ ";
    iter(it, v) os << it->first << ": " << it->second
                   << __sep__[next(it) == v.end()];
    return os <<  "}";
}
KV ostream &operator<<(ostream &os, const pair<K, V> &v) {
    return os << "(" << v.first << __sep__[0] << v.second << ")"; 
}
KV ostream &operator<<(ostream &os, const tuple<K, V> &v) {
    return os << "(" << tget(v, 0) << __sep__[0] << tget(v, 1) << ")";
}
KVT ostream &operator<<(ostream &os, const tuple<K, V, T> &v) {
    return os << "(" << tget(v, 0) << __sep__[0] << tget(v, 1)
              << __sep__[0] << tget(v, 2) << ")";
}

SOMET void __swrite(const char* sep, const T& x) { cout << x << sep; }
TARGS void __swrite(const char* sep, const T& x, Args... a) { cout << x << sep; __swrite(sep, a...); }

ARGS void writeln(Args... a) { __swrite("\n", a...); }
void writeln() { cout << "\n"; }

ARGS void writes(Args... a) { __swrite(" ", a...); }
ARGS void writesln(Args... a) { __swrite(" ", a...); writeln();}
ARGS void write(Args... a) { __swrite("", a...); }

TARGS void mkmax(T& a, Args&&... z) { a = max({a, z...}); }
TARGS void mkmin(T& a, Args&&... z) { a = min({a, z...}); }

int log2_floor(unsigned int n) { return 31 - clz(n); }
#define binrep(n)       bitset<32>((uint)n)
// clang-format on
class rng {
    mt19937 mtgen;
    uniform_int_distribution<int> dist_;

  public:
    rng(int min, int max, size_t seed = random_device()())
        : mtgen(seed), dist_(min, max) {}
    int operator()() { return dist_(mtgen); }
};

vector<int> randomvec(int sz) {
    rng rg(0, 10);
    vi s;
    rep(i, sz) s += rg();
    return s;
}

string randomstring(int sz) {
    rng rg((int)'a', (int)'z');
    string s;
    rep(i, sz) s += (char)rg();
    return s;
}

#ifdef JJ
#define put(x)                                                                 \
    {                                                                          \
        auto __res__ = x;                                                      \
        cout << '#' << (__LINE__) << ": ";                                     \
        cout << #x << " = " << (__res__) << "\n";                              \
    }
#define deb(...)                                                               \
    {                                                                          \
        cout << '#' << (__LINE__) << ": " << #__VA_ARGS__ << " = ";            \
        writes(__VA_ARGS__);                                                   \
        cout << "\n";                                                          \
    }
#define linen                                                                  \
    { cout << '#' << (__LINE__) << ":\n"; }
#define check(x) assert(x)
#else
#define put(x)   /* nothing */
#define linen    /* nothing */
#define deb(...) /* nothing */
#define check(x) /* nothing */
#endif
#define OTC

#define I first
#define J second

void soln() {
    re3int(h, w, k);
    vvi A(h, vi(w, 0));
    rep(i, h) rep(j, w) {
        rechar(c);
        A[i][j] = c - '0';
    }
    vvi wcnts(h + 1, vi(w + 1, 0));
    rep(i, h) rep(j, w) wcnts[i + 1][j + 1] =
        wcnts[i + 1][j] + wcnts[i][j + 1] - wcnts[i][j] + A[i][j];
    auto ccnt = [&](pii p1, pii p2) {
        return wcnts[p2.I][p2.J] - wcnts[p1.I][p2.J] -
               wcnts[p2.I][p1.J] + wcnts[p1.I][p1.J];
    };
    int ans = inf;
    // auto f = [&](int r1, int r2) {
    //     int j1 = 0, j2 = 1;
    //     int cnt = 0;
    //     while (j2 <= w) {
    //         if (ccnt({r1, j1}, {r2, j2}) > k) {
    //             ++cnt;
    //             j1 = j2;
    //         }
    //         ++j2;
    //     }
    //     return cnt;
    // };
    auto ispos = [&](pii p1, pii p2) { return ccnt(p1, p2) <= k; };
    rep(sp, 1 << (h - 1)) {
        vi hcuts{0};
        auto bs = binrep(sp);
        int cuts = pct(sp);
        rev(i, h - 1) if (bs[i] != 0) hcuts += h - 1 - i;
        hcuts += h;
        // deb(hcuts, cuts, binrep(sp));
        // rep(i, ~hcuts - 1) cuts += ispos(hcuts[i], hcuts[i + 1]);
        int j1 = 0, j2 = 1;
        while (j2 <= w) {
            auto ok = true;
            rep(i, ~hcuts - 1) {
                if (!ispos({hcuts[i], j1}, {hcuts[i + 1], j2})) {
                    // [j1, j2) is not ok
                    ok = false;
                    break;
                }
            }
            if (!ok) {
                // smallest cut impossible
                if (j2 == j1 + 1) {
                    cuts = inf;
                    break;
                } else {
                    // cut [j1, j2-1) next => [j2-1,..)
                    cuts += 1;
                    j1 = j2-1;
                    // ++j2;
                }
            } else {
                // try a bigger vcut
                ++j2;
            }
        }
        mkmin(ans, cuts);
    }
    writeln(ans);
}
int main() {
#ifndef JJ
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#endif
#ifdef OTC
    soln();
#else
    int tc;
    cin >> tc;
    for (int i = 0; i < tc; ++i) { soln(); }
#endif
}


Measured memory_bytes: 384