CQXYM found a rectangle A of size n × m. There are n rows and m columns of blocks. Each block of the rectangle is an obsidian block or empty. CQXYM can change an obsidian block to an empty block or an empty block to an obsidian block in one operation.

A rectangle M size of a × b is called a portal if and only if it satisfies the following conditions:

  * a ≥ 5,b ≥ 4. 
  * For all 1 < x < a, blocks M_{x,1} and M_{x,b} are obsidian blocks. 
  * For all 1 < x < b, blocks M_{1,x} and M_{a,x} are obsidian blocks. 
  * For all 1<x<a,1<y<b, block M_{x,y} is an empty block. 
  * M_{1, 1}, M_{1, b}, M_{a, 1}, M_{a, b} can be any type. 

Note that the there must be a rows and b columns, not b rows and a columns.

Note that corners can be any type

CQXYM wants to know the minimum number of operations he needs to make at least one sub-rectangle a portal.

Input

The first line contains an integer t (t ≥ 1), which is the number of test cases.

For each test case, the first line contains two integers n and m (5 ≤ n ≤ 400, 4 ≤ m ≤ 400). 

Then n lines follow, each line contains m characters 0 or 1. If the j-th character of i-th line is 0, block A_{i,j} is an empty block. Otherwise, block A_{i,j} is an obsidian block.

It is guaranteed that the sum of n over all test cases does not exceed 400.

It is guaranteed that the sum of m over all test cases does not exceed 400.

Output

Output t answers, and each answer in a line.

Examples

Input


1
5 4
1000
0000
0110
0000
0001


Output


12


Input


1
9 9
001010001
101110100
000010011
100000001
101010101
110001111
000001111
111100000
000110000


Output


5

Note

In the first test case, the final portal is like this:
    
    
      
    1110  
    1001  
    1001  
    1001  
    0111  
    
import static java.lang.Math.*;

public class A {

	public Object solve () {
		int N = sc.nextInt(), M = sc.nextInt();
		int [][] A = new int [N][];
		for (int i : rep(N))
			A[i] = toDigits(sc.next());

		int [][] B = new int [N][M];
		for (int i : rep(N))
			for (int j : rep(M))
				B[i][j] = 1 - A[i][j];

		MatrixRangeSum S = new MatrixRangeSum(A), T = new MatrixRangeSum(B);
		int res = INF;

		for (int a : rep(N))
			for (int b : rep(M))
				for (int c = a+4; c < N; ++c) {
					int f = T.get(a+1, b, c, b+1);
					if (f >= res)
						break;

					for (int d = b+3; d < M; ++d) {
						int g = T.get(a, b+1, a+1, d);
						int h = S.get(a+1, b+1, c, d);

						if (f + g + h >= res)
							break;

						int f2 = T.get(a+1, d, c, d+1);
						int g2 = T.get(c, b+1, c+1, d);

						int r = f + g + h + f2 + g2;
						res = min(res, r);
					}
				}

		return res;
	}

	private static final int CONTEST_TYPE = 2;

	private static void init () {
	}

	private static final int INF = (int) 1e9 + 10;
	private static int [] rep (int N) { return rep(0, N); }
	private static int [] rep (int S, int T) { if (S >= T) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static int [] toDigits (String S) { return toInts(S.toCharArray(), '0'); }
	private static int [] toInts (char [] A, char S) { int [] res = new int [A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i] - S; return res; }
	private static class MatrixRangeSum {
		private final int [][] S;
		public int get(int r1, int c1, int r2, int c2) { return S[r2][c2] - S[r1][c2] - S[r2][c1] + S[r1][c1]; }
		public MatrixRangeSum (int [][] A) {
			int R = A.length, C = A[0].length;
			S = new int [R+1][C+1];
			for (int i = 1; i <= R; ++i)
				for (int j = 1; j <= C; ++j)
					S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i-1][j-1];
		}
	}
	//////////////////////////////////////////////////////////////////////////////////// OFF
	private static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static class IOUtils {
		public static class MyScanner {
			public String next () { newLine(); return line[index++]; }
			public int nextInt () { return Integer.parseInt(next()); }
			//////////////////////////////////////////////
			private boolean eol () { return index == line.length; }
			private String readLine () {
				try {
					int b;
					StringBuilder res = new StringBuilder();
					while ((b = System.in.read()) < ' ')
						continue;
					res.append((char)b);
					while ((b = System.in.read()) >= ' ')
						res.append((char)b);
					return res.toString();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private MyScanner () {
				try {
					while (System.in.available() == 0)
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine () {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private String [] split (String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build (Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim (String delim, Object o, Object ... A) {
			java.util.List<String> str = new java.util.ArrayList<>();
			append(str, o);
			for (Object p : A)
				append(str, p);
			return String.join(delim, str.toArray(new String [0]));
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static java.text.DecimalFormat formatter = new java.text.DecimalFormat("#.#########");
		private static void start () { if (t == 0) t = millis(); }
		private static void append (java.util.function.Consumer<Object> f, java.util.function.Consumer<Object> g, Object o) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					f.accept(java.lang.reflect.Array.get(o, i));
			}
			else if (o instanceof Iterable<?>)
				((Iterable<?>)o).forEach(f::accept);
			else
				g.accept(o instanceof Double ? formatter.format(o) : o);
		}
		private static void append (java.util.List<String> str, Object o) {
			append(x -> append(str, x), x -> str.add(x.toString()), o);
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void flush () { pw.flush(); System.out.flush(); }
		private static void print (Object o, Object ... A) {
			String res = build(o, A);
			if (DEBUG == 2)
				err(res, '(', time(), ')');
			if (res.length() > 0)
				pw.println(res);
			if (DEBUG == 1)
				flush();
		}
		private static void err (Object o, Object ... A) { System.err.println(build(o, A)); }
		private static int DEBUG;
		private static void exit () {
			String end = "------------------" + System.lineSeparator() + time();
			switch(DEBUG) {
			case 1: print(end); break;
			case 2: err(end); break;
			}
			IOUtils.pw.close();
			System.out.flush();
			System.exit(0);
		}
		private static long t;
		private static long millis () { return System.currentTimeMillis(); }
		private static String time () { return "Time: " + (millis() - t) / 1000.0; }
		private static void run (int N) {
			try { DEBUG = Integer.parseInt(System.getProperties().get("DEBUG").toString()); }
			catch (Throwable t) {}

			for (int n = 1; n <= N; ++n) {
				Object res = new A().solve();
				if (res != null) {
					@SuppressWarnings("all")
					Object o = CONTEST_TYPE == 0 ? "Case #" + n + ": " + build(res) : res;
					print(o);
				}
			}
			exit();
		}
	}
	////////////////////////////////////////////////////////////////////////////////////
	public static void main (String[] args) {
		@SuppressWarnings("all")
		int N = CONTEST_TYPE == 1 ? 1 : sc.nextInt();
		init();
		IOUtils.run(N);
	}
}
