Untitled

package dao_cot;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Calendar;
import java.util.Scanner;

public class Solution {
	static int dem =0;
	static int n, m, k, res;
	static int[][] a;
	static int[] sw;

	static int countRes() {
		int dem = 0, check;
		for (int i = 0; i < n; i++) {
			check = 1;
			for (int j = 0; j < m; j++) {
				if ((a[i][j] + sw[j]) % 2 == 0) {
					check = 0;
					break;
				}
			}
			if (check == 1) {
				dem++;
			}
		}
		return dem;
	}

	static void backtrack(int col, int count) {
		dem++;
		// System.out.println(col + " " + count);
		
		

		if (col == m) {
			if ((k % 2 == 0 && count % 2 == 0)
					|| (k % 2 == 1 && count % 2 == 1)) {
				int x = countRes();	
				res = res < x ? x : res;
			}
			return;
		}
		if (count == k) {
			int x = countRes();
			res = res < x ? x : res;
			return;
		}

		for (int i = 0; i < 2; i++) {
			sw[col] = i;
			backtrack(col + 1, count + i);
			sw[col] = 0;
		}

	}

	public static void main(String[] args) {
		long start = Calendar.getInstance().getTimeInMillis();
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			m = scanner.nextInt();
			k = scanner.nextInt();
			a = new int[n][m];
			sw = new int[m];
			res = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					a[i][j] = scanner.nextInt();
				}
			}

			backtrack(0, 0);

			System.out.println("Case #" + t + " " + res);
		}
		System.out.println(dem);
		scanner.close();
		long end = Calendar.getInstance().getTimeInMillis();
		System.out.println(end - start);
	}
}