You are given an empty grid with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). You should fill this grid with integers in a way that satisfies the following rules:
- For any three cells $c_1$, $c_2$ and $c_3$ such that $c_1$ shares a side with $c_2$ and another side with $c_3$, the integers written in cells $c_2$ and $c_3$ are distinct.
- Let's denote the number of different integers in the grid by $K$; then, each of these integers should lie between $1$ and $K$ inclusive.
- $K$ should be minimum possible.
Find the minimum value of $K$ and a resulting (filled) grid. If there are multiple solutions, you may find any one.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $M$.

-----Output-----
- For each test case, print $N+1$ lines.
- The first line should contain a single integer — the minimum $K$.
- Each of the following $N$ lines should contain $M$ space-separated integers between $1$ and $K$ inclusive. For each valid $i, j$, the $j$-th integer on the $i$-th line should denote the number in the $i$-th row and $j$-th column of the grid.

-----Constraints-----
- $1 \le T \le 500$
- $1 \le N, M \le 50$
- the sum of $N \cdot M$ over all test cases does not exceed $7 \cdot 10^5$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
2
1 1
2 3

-----Example Output-----
1
1
3
1 1 2
2 3 3

-----Explanation-----
Example case 1: There is only one cell in the grid, so the only valid way to fill it is to write $1$ in this cell. Note that we cannot use any other integer than $1$.
Example case 2: For example, the integers written in the neighbours of cell $(2, 2)$ are $1$, $2$ and $3$; all these numbers are pairwise distinct and the integer written inside the cell $(2, 2)$ does not matter. Note that there are pairs of neighbouring cells with the same integer written in them, but this is OK.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Implementation

Constructive algorithms

Starter code:

Solutions:
T = int(input())
for test in range(0, T):
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	tem = 0
	if n != 1 and m != 1:
		t1 = n
		t2 = m
		n = n + n % 2
		m = m + m % 2
		c1 = 0
		grid1 = [[]]
		c2 = 0
		grid2 = [[]]
		for i in range(0, m):
			temp = (i + 2) // 2
			if temp % 2 == 1:
				grid1[0].append(1)
			else:
				grid1[0].append(2)
		if m > 2:
			c1 = 2
		else:
			c1 = 1
		for i in range(1, n):
			grid1.append([])
			for j in range(0, m):
				l = []
				if i - 1 >= 0 and j - 1 >= 0:
					l.append(grid1[i - 1][j - 1])
				if i - 1 >= 0 and j + 1 < m:
					l.append(grid1[i - 1][j + 1])
				if j - 2 >= 0:
					l.append(grid1[i][j - 2])
				if i - 2 >= 0:
					l.append(grid1[i - 2][j])
				f = 0
				for x in range(1, c1 + 1):
					l.append(x)
					if l.index(x) == len(l) - 1:
						f = 1
						break
				if f == 1:
					grid1[i].append(x)
				else:
					c1 = c1 + 1
					grid1[i].append(c1)
		for i in range(0, n):
			temp = (i + 2) // 2
			if temp % 2 == 1:
				grid2[0].append(1)
			else:
				grid2[0].append(2)
		if n > 2:
			c2 = 2
		else:
			c2 = 1
		for i in range(1, m):
			grid2.append([])
			for j in range(0, n):
				l = []
				if i - 1 >= 0 and j - 1 >= 0:
					l.append(grid2[i - 1][j - 1])
				if i - 1 >= 0 and j + 1 < n:
					l.append(grid2[i - 1][j + 1])
				if j - 2 >= 0:
					l.append(grid2[i][j - 2])
				if i - 2 >= 0:
					l.append(grid2[i - 2][j])
				f = 0
				for x in range(1, c2 + 1):
					l.append(x)
					if l.index(x) == len(l) - 1:
						f = 1
						break
				if f == 1:
					grid2[i].append(x)
				else:
					c2 = c2 + 1
					grid2[i].append(c2)
		n = t1
		m = t2
		if c1 <= c2:
			print(c1)
			for i in range(0, n):
				for j in range(0, m - 1):
					print(grid1[i][j], end=' ')
				print(grid1[i][m - 1])
		else:
			print(c2)
			for i in range(0, n):
				for j in range(0, m - 1):
					print(grid2[j][i], end=' ')
				print(grid2[m - 1][i])
	elif n == 1:
		if m > 2:
			print(2)
		else:
			print(1)
		for i in range(0, m - 1):
			temp = (i + 2) // 2
			if temp % 2 == 1:
				print(1, end=' ')
			else:
				print(2, end=' ')
		if (m + 1) // 2 % 2 == 1:
			print(1)
		else:
			print(2)
	else:
		if n > 2:
			print(2)
		else:
			print(1)
		for i in range(0, n):
			temp = (i + 2) // 2
			if temp % 2 == 1:
				print(1)
			else:
				print(2)


t = int(input())
for w in range(t):
	inp = list(map(int, input().split()))
	row = inp[0]
	col = inp[1]
	flag = 0
	if min(row, col) == 1:
		if max(row, col) >= 3:
			print(2)
		else:
			print(1)
		if 1:
			a = [0 for i in range(max(col, row))]
			count = 0
			it = 1
			for i in range(max(col, row)):
				if count == 2:
					if it == 1:
						it = 2
					else:
						it = 1
					a[i] = it
					count = 1
					continue
				else:
					a[i] = it
					count += 1
			if row == 1:
				for item in a:
					print(item, end=' ')
				print(' ')
			else:
				for item in a:
					print(item)
	elif min(row, col) == 2:
		if max(row, col) == 2:
			print(2)
			print(2, end=' ')
			print(2)
			print(1, end=' ')
			print(1)
		else:
			a = [[0 for i in range(max(row, col))] for j in range(2)]
			print(3)
			it = 3
			count = 1
			for i in range(max(row, col)):
				if count == 1:
					a[0][i] = it
					count += 1
					continue
				elif count == 2:
					it -= 1
					if it == 0:
						it = 3
					a[0][i] = it
					count = 1
					continue
			it = 2
			count = 2
			for i in range(max(row, col)):
				if count == 1:
					a[1][i] = it
					count += 1
					continue
				elif count == 2:
					it -= 1
					if it == 0:
						it = 3
					a[1][i] = it
					count = 1
					continue
			if row == 2:
				for i in range(max(row, col)):
					print(a[0][i], end=' ')
				print(' ')
				for i in range(max(row, col)):
					print(a[1][i], end=' ')
				print(' ')
			else:
				for i in range(max(row, col)):
					print(a[0][i], end=' ')
					print(a[1][i])
	else:
		print(4)
		a = [[0 for i in range(col)] for j in range(row)]
		a[0][0] = 2
		a[1][0] = 2
		a[0][1] = 3
		a[1][1] = 3
		for i in range(2, col, 2):
			if a[0][i - 2] == 2:
				a[0][i] = 1
				a[1][i] = 1
			else:
				a[0][i] = 2
				a[1][i] = 2
		for i in range(3, col, 2):
			if a[0][i - 2] == 3:
				a[0][i] = 4
				a[1][i] = 4
			else:
				a[0][i] = 3
				a[1][i] = 3
		for i in range(col):
			for j in range(2, row):
				if a[j - 2][i] == 2:
					a[j][i] = 1
				elif a[j - 2][i] == 1:
					a[j][i] = 2
				elif a[j - 2][i] == 3:
					a[j][i] = 4
				elif a[j - 2][i] == 4:
					a[j][i] = 3
		for i in range(row):
			for j in range(col):
				print(a[i][j], end=' ')
			print(' ')


li = [1, 2, 3, 4]
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	if m == 1:
		if n > 2:
			print(2)
		else:
			print(1)
		for i in range(n):
			print(i // 2 % 2 + 1, end=' ')
		print()
	elif n == 1:
		if m > 2:
			print(2)
		else:
			print(1)
		for i in range(m):
			print(i // 2 % 2 + 1)
	elif m == 2:
		if n > 2:
			print(3)
		else:
			print(2)
		for i in range(n):
			print(i % 3 + 1, end=' ')
		print()
		for i in range(n):
			print(i % 3 + 1, end=' ')
		print()
	elif n == 2:
		if m > 2:
			print(3)
		else:
			print(2)
		for i in range(m):
			print(i % 3 + 1, i % 3 + 1)
	else:
		print(4)
		li = [[1, 1, 3, 3], [2, 2, 4, 4], [3, 3, 1, 1], [4, 4, 2, 2]]
		for i in range(m):
			for j in range(n):
				print(li[i % 4][j % 4], end=' ')
			print()


for _ in range(int(input())):
	ans = []
	(n, m) = [int(x) for x in input().rstrip().split(' ')]
	if n * m == 1:
		print(1)
		print(1)
		continue
	if m == 1 and n > 1:
		if n == 2:
			print(1)
			print(1)
			print(1)
			continue
		print(2)
		ans = [1 for x in range(n + 1)]
		for i in range(2, n + 1, 4):
			ans[i] = 2
		for i in range(3, n + 1, 4):
			ans[i] = 2
		for i in range(n):
			print(ans[i])
		continue
	if n == 1 and m > 1:
		if m == 2:
			print(1)
			print(1, end=' ')
			print(1)
			continue
		print(2)
		ans = [1 for x in range(m + 1)]
		for i in range(2, m + 1, 4):
			ans[i] = 2
		for i in range(3, m + 1, 4):
			ans[i] = 2
		for i in range(m):
			print(ans[i], end=' ')
		print()
		continue
	if n == 2 and m > 1:
		if m == 2:
			print(2)
			print(1, end=' ')
			print(1)
			print(2, end=' ')
			print(2)
			continue
		print(3)
		one = [1 for x in range(m + 1)]
		two = [2 for x in range(m + 1)]
		for i in range(2, m + 1, 6):
			one[i] = 2
			two[i - 1] = 3
		for i in range(3, m + 1, 6):
			one[i] = 2
			two[i - 1] = 3
		for i in range(4, m + 1, 6):
			one[i] = 3
			two[i - 1] = 1
		for i in range(5, m + 1, 6):
			one[i] = 3
			two[i - 1] = 1
		ans.append(one)
		ans.append(two)
		for i in range(n):
			for j in range(m):
				print(ans[i][j], end=' ')
			print()
		continue
	if n > 2 and m == 2:
		(n, m) = (m, n)
		print(3)
		one = [1 for x in range(m + 1)]
		two = [2 for x in range(m + 1)]
		for i in range(2, m + 1, 6):
			one[i] = 2
			two[i - 1] = 3
		for i in range(3, m + 1, 6):
			one[i] = 2
			two[i - 1] = 3
		for i in range(4, m + 1, 6):
			one[i] = 3
			two[i - 1] = 1
		for i in range(5, m + 1, 6):
			one[i] = 3
			two[i - 1] = 1
		ans.append(one)
		ans.append(two)
		for i in range(m):
			print(ans[0][i], end=' ')
			print(ans[1][i])
		continue
	print(4)
	one = [1 for x in range(m)]
	two = [1 for x in range(m)]
	three = [1 for x in range(m)]
	four = [1 for x in range(m)]
	for i in range(0, m, 4):
		one[i] = 1
		two[i] = 2
		three[i] = 4
		four[i] = 3
	for i in range(1, m, 4):
		one[i] = 1
		two[i] = 2
		three[i] = 4
		four[i] = 3
	for i in range(2, m, 4):
		one[i] = 4
		two[i] = 3
		three[i] = 1
		four[i] = 2
	for i in range(3, m, 4):
		one[i] = 4
		two[i] = 3
		three[i] = 1
		four[i] = 2
	for i in range(0, n, 4):
		ans.append(one)
		ans.append(two)
		ans.append(three)
		ans.append(four)
	for i in range(n):
		for j in range(m):
			print(ans[i][j], end=' ')
		print()


t = int(input())
p2 = [1, 1, 2, 2]
p3 = [1, 2, 3]
p4 = [[1, 1, 2, 2], [3, 3, 4, 4], [2, 2, 1, 1], [4, 4, 3, 3]]
for ti in range(t):
	(n, m) = map(int, input().split())
	if n == 1:
		print(2 if m > 2 else 1)
		for j in range(m):
			print(p2[j % 4], end=' ')
		print()
	elif m == 1:
		print(2 if n > 2 else 1)
		for i in range(n):
			print(p2[i % 4])
	elif n == 2:
		print(3 if m > 2 else 2)
		for j in range(m):
			print(p3[j % 3], end=' ')
		print()
		for j in range(m):
			print(p3[j % 3], end=' ')
		print()
	elif m == 2:
		print(3 if n > 2 else 2)
		for i in range(n):
			print(p3[i % 3], end=' ')
			print(p3[i % 3])
	else:
		print(4)
		for i in range(n):
			for j in range(m):
				print(p4[i % 4][j % 4], end=' ')
			print()


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	k = 0
	if N == 1 and M == 1:
		k = 1
		print(k)
	elif N == 1 or M == 1:
		if N == 2:
			k = 1
			print(k)
		elif M == 2:
			k = 1
			print(k)
		else:
			k = 2
			print(2)
	elif N == 2 and M == 2:
		k = 2
		print(k)
	elif N == 2 or M == 2:
		k = 3
		print(k)
	else:
		k = 4
		print(k)
	a = [0]
	if M == 1:
		for i in range(1, N + 1):
			if i == 1:
				a.append(1)
				print(1)
			elif i % 2 == 0:
				a.append(a[i - 1])
				print(a[i - 1])
			elif i % 2 != 0:
				if a[i - 1] == k:
					a.append(1)
					print(1)
				else:
					a.append(a[i - 1] + 1)
					print(a[i - 1] + 1)
	else:
		p = [0]
		for i in range(N):
			a = [0]
			for j in range(1, M + 1):
				if j == 1 and i == 0:
					a.append(1)
					p.append(1)
					print(1, end=' ')
				elif i == 0 and j > 1 and (j % 2 == 0):
					a.append(a[j - 1])
					p.append(a[j - 1])
					print(a[j - 1], end=' ')
				elif i == 0 and j > 1 and (j % 2 != 0):
					if a[j - 1] == k:
						a.append(1)
						p.append(a[j])
						print(a[j], end=' ')
					else:
						p.append(a[j - 1] + 1)
						a.append(a[j - 1] + 1)
						print(a[j - 1] + 1, end=' ')
				elif i > 0:
					if j >= 3 and a[j - 1] == k and (a[j - 2] == k):
						p.append(1)
						a.append(1)
						print(1, end=' ')
					elif j == M:
						if a[j - 1] == a[j - 2]:
							a.append(a[j - 1] + 1)
							p.append(a[j - 1] + 1)
							print(a[j - 1] + 1, end=' ')
						else:
							a.append(a[j - 1])
							p.append(a[j - 1])
							print(a[j - 1], end=' ')
					elif p[M * (i - 1) + j + 1] != k:
						a.append(p[M * (i - 1) + j + 1] + 1)
						p.append(p[M * (i - 1) + j + 1] + 1)
						print(p[M * (i - 1) + j + 1] + 1, end=' ')
					else:
						p.append(1)
						a.append(1)
						print(1, end=' ')
			print(' ')
quit()


def normalGrid(n, m):
	(res, temp, temp1, temp2, temp3) = ([], [], [], [], [])
	for i in range(m):
		if i % 4 <= 1:
			temp.append(1)
			temp1.append(3)
			temp2.append(2)
			temp3.append(4)
		else:
			temp.append(2)
			temp1.append(4)
			temp2.append(1)
			temp3.append(3)
	for i in range(n):
		if i % 4 == 0:
			res.append(temp)
		elif i % 4 == 1:
			res.append(temp1)
		elif i % 4 == 2:
			res.append(temp2)
		else:
			res.append(temp3)
	for i in res:
		print(*i)

def grid23(n, m):
	(temp, temp1) = ([], [])
	for i in range(m):
		if i % 6 == 0 or i % 6 == 1:
			temp.append(1)
		elif i % 6 == 2 or i % 6 == 3:
			temp.append(2)
		else:
			temp.append(3)
	for i in range(m):
		if i % 6 == 0 or i % 6 == 5:
			temp1.append(2)
		elif i % 6 == 1 or i % 6 == 2:
			temp1.append(3)
		else:
			temp1.append(1)
	print(*temp)
	print(*temp1)

def grid32(n, m):
	(t1, t2, t3, t4, t5, t6) = ([1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2])
	for i in range(n):
		if i % 6 == 0:
			print(*t1)
		elif i % 6 == 1:
			print(*t2)
		elif i % 6 == 2:
			print(*t3)
		elif i % 6 == 3:
			print(*t4)
		elif i % 6 == 4:
			print(*t5)
		else:
			print(*t6)
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	if n >= 3 and m >= 3:
		print('4')
		normalGrid(n, m)
	elif n == 1:
		if m == 1:
			print('1\n1')
		elif m == 2:
			print('1\n1 1')
		elif m >= 3:
			print('2')
			res = []
			for i in range(m):
				if i % 4 == 0 or i % 4 == 1:
					res.append(1)
				else:
					res.append(2)
			print(*res)
	elif n == 2:
		if m == 1:
			print(1)
			print('1\n1')
		elif m == 2:
			print(2)
			print('1 1\n2 2')
		elif m >= 3:
			print('3')
			grid23(n, m)
	elif n >= 3:
		if m == 1:
			print('2')
			(res, temp, temp1) = ([], [1], [2])
			for i in range(n):
				if i % 4 == 1 or i % 4 == 0:
					res.append(temp)
				else:
					res.append(temp1)
			for i in res:
				print(*i)
		elif m == 2:
			print('3')
			grid32(n, m)


def fill_grid_max():
	A = [[0 for j in range(50)] for i in range(50)]
	B = [[1, 1, 2, 2], [3, 3, 4, 4], [2, 2, 1, 1], [4, 4, 3, 3]]
	for i in range(50):
		for j in range(50):
			A[i][j] = B[i % 4][j % 4]
	return A

def calculate_k(A):
	k = 0
	for row in A:
		k = max(k, max(row))
	return k

def print_output(A, k, n, m):
	print(k)
	for i in range(n):
		for j in range(m):
			print(A[i][j], end=' ')
		print()
t = int(input())
A = fill_grid_max()
for test in range(t):
	(n, m) = map(int, input().split())
	if n == 1 and m == 1:
		print(1)
		print(1)
	elif n == 1:
		B = A[0][:m]
		k = max(B)
		print(k)
		for x in B:
			print(x, end=' ')
		print()
	elif m == 1:
		B = [[] for x in range(n)]
		for i in range(n):
			B[i].append(A[0][i])
		k = max(A[0][:n])
		print_output(B, k, n, m)
	elif n == 2 and m == 2:
		k = 2
		B = [[1, 1], [2, 2]]
		print_output(B, k, n, m)
	elif n == 2:
		k = 3
		B = [[0 for x in range(m)] for y in range(n)]
		C = [[1, 2, 3], [1, 2, 3]]
		for i in range(n):
			for j in range(m):
				B[i][j] = C[i][j % 3]
		print_output(B, k, n, m)
	elif m == 2:
		k = 3
		B = [[0 for x in range(m)] for y in range(n)]
		C = [[1, 1], [2, 2], [3, 3]]
		for i in range(n):
			for j in range(m):
				B[i][j] = C[i % 3][j]
		print_output(B, k, n, m)
	if n >= 3 and m >= 3:
		print_output(A, 4, n, m)


def update(grid, i, j, k):
	used = [0] * 6
	if j - 2 >= 0:
		used[grid[i][j - 2]] = 1
	if i - 2 >= 0:
		used[grid[i - 2][j]] = 1
	if i - 1 >= 0 and j - 1 >= 0:
		used[grid[i - 1][j - 1]] = 1
	if i - 1 >= 0 and j + 1 < len(grid[0]):
		used[grid[i - 1][j + 1]] = 1
	for fill in range(1, 5):
		if used[fill] == 0:
			if fill > k:
				k = fill
			grid[i][j] = fill
			return k
	grid[i][j] = 5
	return 5
grid5050 = [[0] * 50 for row in range(50)]
k = 1
for i in range(50):
	for j in range(50):
		k = update(grid5050, i, j, k)
noOfCases = int(input())
for case in range(noOfCases):
	(n, m) = list(map(int, input().split()))
	k = 1
	grid = [[0] * m for row in range(n)]
	if n >= 3 and m >= 3:
		k = 4
		for i in range(n):
			for j in range(m):
				grid[i][j] = grid5050[i][j]
	elif n == 2 and m > 2:
		k = 3
		for j in range(m):
			next = j % 3 + 1
			grid[0][j] = next
			grid[1][j] = next
	else:
		for i in range(n):
			for j in range(m):
				k = update(grid, i, j, k)
	print(k)
	print('\n'.join([''.join([str(item) + ' ' for item in row]) for row in grid]))


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().strip().split(' '))
	if min(n, m) >= 3:
		p1 = [0] * m
		p2 = [0] * m
		p3 = [0] * m
		p4 = [0] * m
		for i in range(0, m, 2):
			if i % 4 == 2:
				p1[i] = 2
				p2[i] = 1
				p3[i] = 4
				p4[i] = 3
				if i + 1 < m:
					p1[i + 1] = 2
					p2[i + 1] = 1
					p3[i + 1] = 4
					p4[i + 1] = 3
			elif i % 4 == 0:
				p1[i] = 1
				p2[i] = 2
				p3[i] = 3
				p4[i] = 4
				if i + 1 < m:
					p1[i + 1] = 1
					p2[i + 1] = 2
					p3[i + 1] = 3
					p4[i + 1] = 4
		print(4)
		for i in range(n):
			if i % 4 == 0:
				print(*p1)
			elif i % 4 == 1:
				print(*p3)
			elif i % 4 == 2:
				print(*p2)
			else:
				print(*p4)
	elif m == n and m == 2:
		print(2)
		p1 = [1, 1]
		p2 = [2, 2]
		print(*p1)
		print(*p2)
	elif m != n and min(m, n) == 2:
		p1 = [0] * max(m, n)
		p2 = [0] * max(m, n)
		for i in range(0, max(m, n), 2):
			if i % 6 == 4:
				p1[i] = 3
				p2[i] = 2
				if i + 1 < len(p1):
					p1[i + 1] = 3
					p2[i + 1] = 2
			elif i % 6 == 2:
				p1[i] = 2
				p2[i] = 1
				if i + 1 < len(p1):
					p1[i + 1] = 2
					p2[i + 1] = 1
			elif i % 6 == 0:
				p1[i] = 1
				p2[i] = 3
				if i + 1 < len(p1):
					p1[i + 1] = 1
					p2[i + 1] = 3
		del p2[-1]
		p2 = [2] + p2
		print(3)
		if n == 2:
			print(*p1)
			print(*p2)
		else:
			for i in range(max(m, n)):
				print(p1[i], p2[i])
	elif n == 1 or m == 1:
		p1 = [0] * max(m, n)
		for i in range(0, max(m, n), 2):
			if i % 4 == 2:
				p1[i] = 2
				if i + 1 < max(m, n):
					p1[i + 1] = 2
			elif i % 4 == 0:
				p1[i] = 1
				if i + 1 < max(m, n):
					p1[i + 1] = 1
		if 2 in p1:
			print(2)
		else:
			print(1)
		if n == 1:
			print(*p1)
		else:
			for c in p1:
				print(c)


lst = [1, 2, 3, 4]
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	ans = [[0 for i in range(m)] for i in range(n)]
	k = 0
	if n == 1:
		if m > 2:
			print(2)
		else:
			print(1)
		for i in range(m):
			print(i // 2 % 2 + 1)
	elif m == 1:
		if n > 2:
			print(2)
		else:
			print(1)
		for i in range(n):
			print(i // 2 % 2 + 1, end=' ')
	elif n == 2:
		if m > 2:
			print(3)
		else:
			print(2)
		for i in range(m):
			print(i % 3 + 1, i % 3 + 1)
	elif m == 2:
		if n > 2:
			print(3)
		else:
			print(2)
		for i in range(n):
			print(i % 3 + 1, end=' ')
		print()
		for i in range(n):
			print(i % 3 + 1, end=' ')
	else:
		print(4)
		lst = [[1, 1, 3, 3], [2, 2, 4, 4], [3, 3, 1, 1], [4, 4, 2, 2]]
		for i in range(m):
			for j in range(n):
				print(lst[i % 4][j % 4], end=' ')


t = int(input())
for i in range(t):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	if n == 1 and m == 1:
		print(1)
		print(1)
	elif n == 1 and m == 2:
		print(1)
		print(1, 1)
	elif n == 2 and m == 1:
		for i in range(3):
			print(1)
	elif n == 2 and m == 2:
		print(2)
		print(1, 1)
		print(2, 2)
	elif n == 1:
		print(2)
		ans = [1, 1, 2, 2]
		for i in range(m):
			print(ans[i % 4], end=' ')
		print()
	elif m == 1:
		print(2)
		ans = [1, 1, 2, 2]
		for i in range(n):
			print(ans[i % 4])
	elif m == 2:
		print(3)
		l = [[1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2]]
		for i in range(n):
			print(l[i % 6][0], l[i % 6][1])
	elif n == 2:
		print(3)
		l = [[1, 1, 2, 2, 3, 3], [2, 3, 3, 1, 1, 2]]
		for i in range(m):
			print(l[0][i % 6], end=' ')
		print()
		for i in range(m):
			print(l[1][i % 6], end=' ')
		print()
	else:
		print(4)
		for i in range(n):
			if i % 4 == 0 or i % 4 == 1:
				ans = [1, 2, 3, 4]
			else:
				ans = [3, 4, 1, 2]
			for j in range(m):
				print(ans[j % 4], end=' ')
			print()


t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	c1 = c
	if c % 2 == 1:
		c1 = c + 1
		mat = [[0] * (c + 1) for _ in range(r)]
	else:
		mat = [[0] * c for _ in range(r)]
	k1 = 1
	for i in range(r):
		for j in range(c1):
			arr = [0] * 6
			if i - 2 >= 0:
				v = mat[i - 2][j]
				arr[v] = 1
			if j - 2 >= 0:
				v = mat[i][j - 2]
				arr[v] = 1
			if i - 1 >= 0 and j - 1 >= 0:
				v = mat[i - 1][j - 1]
				arr[v] = 1
			if i - 1 >= 0 and j + 1 < c1:
				v = mat[i - 1][j + 1]
				arr[v] = 1
			for k in range(1, 6):
				if arr[k] == 0:
					mat[i][j] = k
					if k1 < k:
						k1 = k
					break
	(n, m) = (c, r)
	m1 = m
	if m % 2 == 1:
		m1 = m + 1
		mat1 = [[0] * (m + 1) for _ in range(n)]
	else:
		mat1 = [[0] * m for _ in range(n)]
	k2 = 1
	for i in range(n):
		for j in range(m1):
			arr = [0] * 6
			if i - 2 >= 0:
				v = mat1[i - 2][j]
				arr[v] = 1
			if j - 2 >= 0:
				v = mat1[i][j - 2]
				arr[v] = 1
			if i - 1 >= 0 and j - 1 >= 0:
				v = mat1[i - 1][j - 1]
				arr[v] = 1
			if i - 1 >= 0 and j + 1 < m1:
				v = mat1[i - 1][j + 1]
				arr[v] = 1
			for k in range(1, 6):
				if arr[k] == 0:
					mat1[i][j] = k
					if k2 < k:
						k2 = k
					break
	if k1 <= k2:
		print(k1)
		for l in mat:
			l = l[:c]
			print(' '.join(map(str, l)))
	else:
		if m1 > m:
			for (i, l) in enumerate(mat1):
				mat1[i] = l[:m]
		mat2 = [[mat1[j][i] for j in range(n)] for i in range(m)]
		print(k2)
		for l in mat2:
			print(' '.join(map(str, l)))


import sys
f = sys.stdin
t = int(f.readline())
for r in range(t):
	(n, m) = map(int, f.readline().rstrip().split())
	if n == 1 and m == 1:
		print('1')
		print('1')
	elif n == 2 and m == 2:
		print('2')
		print('1 2')
		print('1 2')
	elif n == 2 and m == 1:
		print('1')
		print('1')
		print('1')
	elif n == 1 and m == 2:
		print('1')
		print('1 1')
	elif n == 1 and m > 2:
		print('2')
		for i in range(1, m + 1):
			if i % 4 == 1 or i % 4 == 2:
				print('1', end=' ')
			else:
				print('2', end=' ')
	elif n > 2 and m == 1:
		print('\n2')
		for i in range(1, n + 1):
			if i % 4 == 1 or i % 4 == 2:
				print('1')
			else:
				print('2')
	elif n == 2 and m > 2:
		print('3')
		for i in range(0, n):
			for j in range(1, m + 1):
				if j % 3 == 1:
					print('1', end=' ')
				elif j % 3 == 2:
					print('2', end=' ')
				else:
					print('3', end=' ')
			print()
	elif n > 2 and m == 2:
		print('3')
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if i % 3 == 1:
					print('1', end=' ')
				elif i % 3 == 2:
					print('2', end=' ')
				else:
					print('3', end=' ')
			print()
	else:
		print('4')
		l = [[0 for x in range(m)] for x in range(n)]
		for q in range(0, m):
			if (q + 1) % 4 != 0:
				l[0][q] = (q + 1) % 4
				l[1][q] = (q + 1) % 4
			else:
				l[0][q] = 4
				l[1][q] = 4
		for i in range(2, n):
			for j in range(1, m - 1):
				l[i][j] = 10 - (l[i - 1][j - 1] + l[i - 2][j] + l[i - 1][j + 1])
			if l[i][1] != 1:
				l[i][0] = l[i][1] - 1
			else:
				l[i][0] = 4
			if l[i][m - 2] != 4:
				l[i][m - 1] = l[i][m - 2] + 1
			else:
				l[i][m - 1] = 1
		for i in range(0, n):
			for j in range(0, m):
				print(l[i][j], end=' ')
			print()


test = int(input())
for k in range(test):
	l = list(map(int, input().split()))
	n = l[0]
	m = l[1]
	if n == 1 and m == 1:
		print(1)
		print(1)
	elif n == 1 and m == 2:
		print(1)
		print(1, 1)
	elif n == 2 and m == 1:
		print(1)
		print(1)
		print(1)
	elif n == 2 and m == 2:
		print(2)
		print(1, 1)
		print(2, 2)
	elif n == 1:
		print(2)
		a = [1, 1, 2, 2]
		for j in range(m):
			print(a[j % 4], end=' ')
		print()
	elif m == 1:
		print(2)
		a = [1, 1, 2, 2]
		for j in range(n):
			print(a[j % 4])
	elif m == 2:
		print(3)
		a = [[1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2]]
		for i in range(n):
			print(a[i % 6][0], a[i % 6][1])
	elif n == 2:
		print(3)
		a = [[1, 1, 2, 2, 3, 3], [2, 3, 3, 1, 1, 2]]
		for i in range(m):
			print(a[0][i % 6], end=' ')
		print()
		for i in range(m):
			print(a[1][i % 6], end=' ')
		print()
	else:
		print(4)
		for i in range(n):
			if i % 4 == 0 or i % 4 == 1:
				a = [1, 2, 3, 4]
			else:
				a = [3, 4, 1, 2]
			for j in range(m):
				print(a[j % 4], end=' ')
			print()


a = []
for i in range(20):
	b = [1, 1, 2, 2]
	b = b * 20
	a.append(b[:50])
	b = [3, 3, 4, 4]
	b = b * 20
	a.append(b[:50])
	b = [2, 2, 1, 1]
	b = b * 20
	a.append(b[:50])
	b = [4, 4, 3, 3]
	b = b * 20
	a.append(b[:50])
a = a[:50]
for _ in range(int(input())):
	[n, m] = [int(i) for i in input().split()]
	if n == 2 and m == 2:
		print(2)
		print(1, 1)
		print(2, 2)
		continue
	if n == 2 and m > 2:
		x = []
		b = [1, 1, 2, 2, 3, 3]
		b *= 20
		b = b[:m]
		x.append(b)
		b = [3, 3, 1, 1, 2, 2]
		b *= 20
		b = [2] + b
		b = b[:m]
		x.append(b)
		print(3)
		print(*x[0])
		print(*x[1])
		continue
	if m == 2 and n > 2:
		x = []
		b = [1, 1, 2, 2, 3, 3]
		b *= 20
		b = b[:n]
		x.append(b)
		b = [3, 3, 1, 1, 2, 2]
		b *= 20
		b = [2] + b
		b = b[:n]
		x.append(b)
		print(3)
		x = zip(*x)
		for i in x:
			print(*i)
		continue
	x = [i[:m] for i in a[:n]]
	y = [i[:n] for i in a[:m]]
	y = list(zip(*y))
	mx = max((max((j for j in i)) for i in x))
	my = max((max((j for j in i)) for i in y))
	if my < mx:
		print(my)
		for i in y:
			print(*i)
	else:
		print(mx)
		for i in x:
			print(*i)


def gencase(n, m):
	print(4)
	ans = [[0 for i in range(m)] for j in range(n)]
	l = [1, 1, 2, 2]
	for i in range(m):
		ans[0][i] = l[i % 4]
	y = 1
	for i in range(1, n):
		ans[i][0] = l[(i + 1) % 4]
	for i in range(1, n):
		for j in range(1, m):
			if ans[i - 1][j - 1] % 2 == 1:
				ans[i][j] = 4 - ans[i - 1][j - 1]
			else:
				ans[i][j] = 6 - ans[i - 1][j - 1]
	for i in range(n):
		for j in range(m):
			print(ans[i][j], end=' ')
		print()

def r1(n, m):
	l = [1, 1, 2, 2]
	if m >= 3:
		print(2)
	else:
		print(1)
	for i in range(m):
		print(l[i % 4], end=' ')
	print()

def r2(n, m):
	if m >= 2:
		print(3)
	else:
		print(2)
	l = [1, 1, 2, 2, 3, 3]
	for i in range(m):
		print(l[i % 6], end=' ')
	print()
	for i in range(m):
		print(l[(i + 3) % 6], end=' ')
	print()

def c1(n, m):
	if n >= 3:
		print(2)
	else:
		print(1)
	l = [1, 1, 2, 2]
	for i in range(n):
		print(l[i % 4])

def c2(n, m):
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		print(3)
	c = 1
	for i in range(n):
		print(c, c)
		c = c + 1
		if c == 4:
			c = 1
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	if m == 2:
		c2(n, m)
	elif n == 1:
		r1(n, m)
	elif m == 1:
		c1(n, m)
	elif n == 2:
		r2(n, m)
	else:
		gencase(n, m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 1 and n == 1:
		print('1\n1')
	elif m == 1 or n == 1:
		if m == 1:
			if n == 2:
				print('1')
			else:
				print('2')
			for i in range(n):
				if int(i / 2) % 2 == 0:
					print('1')
				else:
					print('2')
		else:
			if m == 2:
				print('1')
			else:
				print('2')
			for i in range(m):
				if int(i / 2) % 2 == 0:
					print('1', end=' ')
				else:
					print('2', end=' ')
			print()
	elif m == 2 or n == 2:
		if n == 2 and m == 2:
			print('2\n1 1\n2 2')
		elif n == 2:
			print('3')
			for i in range(m):
				a = i % 6
				if a == 0 or a == 1:
					print('1', end=' ')
				elif a == 2 or a == 3:
					print('2', end=' ')
				else:
					print('3', end=' ')
			print()
			for i in range(m):
				a = i % 6
				if a == 0 or a == 5:
					print('2', end=' ')
				elif a == 1 or a == 2:
					print('3', end=' ')
				else:
					print('1', end=' ')
			print()
		else:
			print('3')
			for i in range(n):
				a = i % 6
				if a == 0:
					print('1 2')
				elif a == 1:
					print('1 3')
				elif a == 2:
					print('2 3')
				elif a == 3:
					print('2 1')
				elif a == 4:
					print('3 1')
				else:
					print('3 2')
	else:
		print('4')
		for i in range(n):
			turn = i % 4
			for j in range(m):
				if turn == 0:
					if int(j / 2) % 2 == 0:
						print('1', end=' ')
					else:
						print('2', end=' ')
				elif turn == 1:
					if int(j / 2) % 2 == 0:
						print('3', end=' ')
					else:
						print('4', end=' ')
				elif turn == 2:
					if int(j / 2) % 2 == 0:
						print('2', end=' ')
					else:
						print('1', end=' ')
				elif int(j / 2) % 2 == 0:
					print('4', end=' ')
				else:
					print('3', end=' ')
			print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	Matrix = [[0 for x in range(m + 5)] for y in range(n + 5)]
	Matrix[0][0] = 1
	if n == 1 and m == 1:
		print(1)
	elif n == 1 and m > 1:
		if m == 2:
			print(1)
		Matrix[0][1] = 1
		if m > 2:
			print(2)
			for i in range(2, m, 2):
				if Matrix[0][i - 2] == 1:
					Matrix[0][i] = 2
				else:
					Matrix[0][i] = 1
			for i in range(3, m, 2):
				if Matrix[0][i - 2] == 1:
					Matrix[0][i] = 2
				else:
					Matrix[0][i] = 1
	elif n > 1 and m == 1:
		Matrix[1][0] = 2
		Matrix[2][0] = 2
		if n == 2:
			print(1)
			Matrix[1][0] = 1
		elif n > 2:
			print(2)
			for i in range(3, n, 2):
				if Matrix[i - 2][0] == 1:
					Matrix[i][0] = 2
				else:
					Matrix[i][0] = 1
			for i in range(4, n, 2):
				if Matrix[i - 2][0] == 1:
					Matrix[i][0] = 2
				else:
					Matrix[i][0] = 1
	elif n == 2 or m == 2:
		if n == 2 and m == 2:
			print(2)
			Matrix[0][1] = 1
			Matrix[1][0] = 2
			Matrix[1][1] = 2
		elif n == 2 and m != 2:
			if m == 1:
				print(1)
				Matrix[1][0] = 1
			elif m > 2:
				print(3)
				Matrix[0][1] = 1
				Matrix[1][0] = 2
				for i in range(2, m):
					if Matrix[0][i - 2] == 1:
						Matrix[0][i] = 2
					elif Matrix[0][i - 2] == 2:
						Matrix[0][i] = 3
					elif Matrix[0][i - 2] == 3:
						Matrix[0][i] = 1
				for i in range(1, m):
					if Matrix[0][i - 1] == 1:
						Matrix[1][i] = 3
					elif Matrix[0][i - 1] == 2:
						Matrix[1][i] = 1
					elif Matrix[0][i - 1] == 3:
						Matrix[1][i] = 2
		elif n != 2 and m == 2:
			if n == 1:
				print(1)
				Matrix[0][1] = 1
			if n > 2:
				print(3)
				Matrix[1][0] = 1
				Matrix[0][1] = 2
				for i in range(2, n):
					if Matrix[i - 2][0] == 1:
						Matrix[i][0] = 2
					elif Matrix[i - 2][0] == 2:
						Matrix[i][0] = 3
					elif Matrix[i - 2][0] == 3:
						Matrix[i][0] = 1
				for i in range(1, n):
					if Matrix[i - 1][0] == 1:
						Matrix[i][1] = 3
					elif Matrix[i - 1][0] == 2:
						Matrix[i][1] = 1
					elif Matrix[i - 1][0] == 3:
						Matrix[i][1] = 2
	elif n > 2 and m > 2:
		print(4)
		Matrix[1][0] = 2
		for i in range(3, n, 2):
			if Matrix[i - 2][0] == 2:
				Matrix[i][0] = 1
			else:
				Matrix[i][0] = 2
		Matrix[2][0] = 2
		for i in range(4, n, 2):
			if Matrix[i - 2][0] == 2:
				Matrix[i][0] = 1
			else:
				Matrix[i][0] = 2
		if m > 5:
			Matrix[0][1] = 1
			Matrix[0][2] = 2
			Matrix[0][3] = 2
			for i in range(4, m, 2):
				if Matrix[0][i - 2] == 2:
					Matrix[0][i] = 1
				else:
					Matrix[0][i] = 2
			for i in range(5, m, 2):
				if Matrix[0][i - 2] == 2:
					Matrix[0][i] = 1
				else:
					Matrix[0][i] = 2
		elif m <= 5:
			Matrix[0][1] = 1
			Matrix[0][2] = 2
			Matrix[0][3] = 2
			Matrix[0][4] = 1
		for i in range(1, n):
			for j in range(1, m):
				if Matrix[i - 1][j - 1] == 1 or Matrix[i - 1][j - 1] == 3:
					if Matrix[i - 1][j - 1] == 3:
						Matrix[i][j] = 1
					else:
						Matrix[i][j] = 3
				elif Matrix[i - 1][j - 1] == 4 or Matrix[i - 1][j - 1] == 2:
					if Matrix[i - 1][j - 1] == 4:
						Matrix[i][j] = 2
					else:
						Matrix[i][j] = 4
	for i in range(n):
		for j in range(m):
			print(Matrix[i][j], end=' ')
		print()


for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = [[0 for x in range(m)] for y in range(n)]
	k = [1, 2, 3, 4]
	if n >= 3 and m >= 3:
		(r, c) = (0, 0)
		while r <= n or c <= m:
			(i, j) = (r, c + 1)
			count = 0
			if r % 2 == 0:
				a = 0
			else:
				a = 2
			while i < m:
				if count == 2:
					count = 0
					if a == 1:
						a = 0
					elif a == 3:
						a = 2
					else:
						a += 1
				l[r][i] = k[a]
				count += 1
				i += 1
			count = 0
			if r % 2 == 0:
				a = 1
			else:
				a = 3
			while j < n:
				l[j][c] = k[a]
				count += 1
				if count == 2:
					count = 0
					if a == 1:
						a = 0
					elif a == 3:
						a = 2
					else:
						a += 1
				j += 1
			r += 1
			c += 1
			if r == n or c == m:
				break
	elif n == 1 and m >= n:
		(a, count) = (0, 0)
		for i in range(m):
			if count == 2:
				count = 0
				if a == 1:
					a = 0
				else:
					a += 1
			l[0][i] = k[a]
			count += 1
	elif m == 2 and n >= m:
		a = 0
		for i in range(n):
			(l[i][0], l[i][1]) = (k[a], k[a])
			if a == 2:
				a = 0
			else:
				a += 1
	elif n == 2 and m >= n:
		for i in range(n):
			count = 0
			if i == 0:
				a = 0
			else:
				a = 2
			for j in range(m):
				if i == 1 and j == 0:
					l[i][j] = k[1]
					continue
				if count == 2:
					count = 0
					if a == 2:
						a = 0
					else:
						a += 1
				l[i][j] = k[a]
				count += 1
	elif m == 1 and n >= m:
		(count, a) = (0, 0)
		for i in range(n):
			if count == 2:
				count = 0
				if a == 1:
					a = 0
				else:
					a += 1
			l[i][0] = k[a]
			count += 1
	print(max(max(l)))
	for i in range(n):
		for j in range(m):
			print(l[i][j], end=' ')
		print()


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	ans = [[0 for i in range(m)] for i in range(n)]
	k = 0
	if n == 1:
		for i in range(m):
			if i % 4 == 0 or i % 4 == 1:
				t = 1
			else:
				t = 2
			ans[0][i] = t
			k = max(k, ans[0][i])
	elif m == 1:
		for i in range(n):
			if i % 4 == 0 or i % 4 == 1:
				t = 1
			else:
				t = 2
			ans[i][0] = t
			k = max(k, ans[i][0])
	elif n == 2:
		t = 1
		for i in range(m):
			ans[0][i] = t
			ans[1][i] = t
			t = t % 3 + 1
			k = max(k, ans[0][i])
	elif m == 2:
		t = 1
		for i in range(n):
			ans[i][0] = t
			ans[i][1] = t
			t = t % 3 + 1
			k = max(k, ans[i][0])
	else:
		for i in range(n):
			if i % 4 == 0 or i % 4 == 1:
				t = 0
			else:
				t = 2
			for j in range(m):
				ans[i][j] = t % 4 + 1
				t += 1
				k = max(k, ans[i][j])
	print(k)
	for i in range(n):
		print(*ans[i])


for _ in range(int(input())):
	(row, col) = map(int, input().split())
	if row == 1 and col == 1:
		print('1\n1')
	elif row == 1:
		if col > 2:
			print(2)
		else:
			print(1)
		ls = [1, 1, 2, 2]
		for i in range(col):
			print(ls[i % 4], end=' ')
		print()
	elif col == 1:
		if row > 2:
			print(2)
		else:
			print(1)
		ls = [1, 1, 2, 2]
		for i in range(row):
			print(ls[i % 4])
	elif col == 2:
		if row == 2:
			print('2\n1 2\n1 2')
		else:
			print(3)
			for j in range(row):
				for i in range(col):
					print(j % 3 + 1, end=' ')
				print()
	elif row == 2:
		if col == 2:
			print('2\n1 2\n1 2')
		else:
			print(3)
			for j in range(2):
				for i in range(col):
					print(i % 3 + 1, end=' ')
				print()
	else:
		first = [1, 1, 2, 2]
		second = [2, 2, 1, 1]
		third = [3, 3, 4, 4]
		fourth = [4, 4, 3, 3]
		first_found = 0
		second_found = 0
		temp = 0
		print(4)
		for i in range(row):
			for j in range(col):
				x = j % 4
				if temp % 2 == 0:
					if first_found == 0:
						print(first[x], end=' ')
					else:
						print(second[x], end=' ')
				elif second_found == 0:
					print(third[x], end=' ')
				else:
					print(fourth[x], end=' ')
			if first_found == 0 and temp % 2 == 0:
				first_found = 1
			elif first_found == 1 and temp % 2 == 0:
				first_found = 0
			if second_found == 0 and temp % 2 == 1:
				second_found = 1
			elif second_found == 1 and temp % 2 == 1:
				second_found = 0
			temp += 1
			print()


def pt(arr):
	for i in arr:
		print(i, end=' ')
	print()
	return 0

def pt1(arr):
	for i in arr:
		print(i)
	return 0

def pt2(a, b):
	for i in range(len(a)):
		print(a[i], b[i])
	return 0
t = int(input())
for _ in range(int(t)):
	(n, m) = map(int, input().split())
	a1 = [[1, 1, 2, 2, 3, 3, 4, 4], [2, 2, 3, 3, 4, 4, 1, 1], [3, 3, 4, 4, 1, 1, 2, 2], [4, 4, 1, 1, 2, 2, 3, 3]]
	a = [1, 2, 3, 4]
	l = []
	if m >= 3 and n >= 3:
		print(4)
		l = a1[0] * (m // 8 + 1)
		pt(l[:m])
		for i in range(n - 1):
			if l[0] == l[1]:
				l = a1[(l[0] + 1) % 4] * (m // 8 + 1)
				l.insert(0, a[l[0] - 2])
				pt(l[:m])
			else:
				l = a1[(l[1] + 1) % 4] * (m // 8 + 1)
				v = a[l[0] - 2]
				l.insert(0, v)
				l.insert(0, v)
				pt(l[:m])
	elif n == 1 or m == 1:
		if n == 1:
			l = [1, 1, 2, 2] * (m // 4 + 1)
			print(max(l[:m]))
			pt(l[:m])
		else:
			l = [1, 1, 2, 2] * (n // 4 + 1)
			print(max(l[:n]))
			pt1(l[:n])
	elif n == 2 and m > 2 or (m == 2 and n > 2):
		print(3)
		if n == 2:
			a1 = [[1, 1, 2, 2, 3, 3], [2, 2, 3, 3, 1, 1], [3, 3, 1, 1, 2, 2]]
			a = [1, 2, 3]
			l = a1[0] * (m // 6 + 1)
			pt(l[:m])
			l = a1[2] * (m // 6 + 1)
			l.insert(0, 2)
			pt(l[:m])
		else:
			a1 = [[1, 1, 2, 2, 3, 3], [2, 2, 3, 3, 1, 1], [3, 3, 1, 1, 2, 2]]
			a = [1, 2, 3]
			l = a1[0] * (n // 6 + 1)
			l1 = a1[2] * (n // 6 + 1)
			l1.insert(0, 2)
			pt2(l[:n], l1[:n])
	else:
		print(2)
		print(1, 1)
		print(2, 2)


def valid(x, y, m, n):
	if 0 <= x < m and 0 <= y < n:
		return 1
	return 0

def neigh(A, x, y, m, n):
	B = []
	if valid(x, y - 2, m, n):
		B.append(A[x][y - 2])
	if valid(x - 2, y, m, n):
		B.append(A[x - 2][y])
	if valid(x - 1, y - 1, m, n):
		B.append(A[x - 1][y - 1])
	if valid(x - 1, y + 1, m, n):
		B.append(A[x - 1][y + 1])
	return set(B)
AA = [[1, 1, 2, 2], [1, 1, 2, 3], [1, 2, 2, 3], [1, 2, 3, 3], [1, 2, 2, 1], [1, 2, 3, 1], [1, 2, 3, 4]]
t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	if m >= 3 and n >= 3:
		P = set(range(1, 5))
	elif m == 1 and n == 1:
		P = set(range(1, 2))
	elif m + n == 3:
		P = set(range(1, 2))
	elif m == 1 or n == 1:
		P = set(range(1, 3))
	elif m == 2 and n == 2:
		P = set(range(1, 3))
	elif m == 2 or n == 2:
		P = set(range(1, 4))
	A = [[0 for j in range(n)] for k in range(m)]
	pk = 0
	if m == 1:
		A[0][0] = 1
		for j in range(1, n):
			B = neigh(A, 0, j, m, n)
			A[0][j] = min(P - B)
		print(max(P))
		for j in A[0]:
			print(j, end=' ')
		print()
		continue
	while True:
		trig = 0
		if max(P) == 4:
			for j in range(n):
				A[0][j] = AA[pk][j % 4]
		else:
			for j in range(n):
				A[0][j] = j % max(P) + 1
		for j in range(1, m):
			for k in range(n):
				B = neigh(A, j, k, m, n)
				if P - B == set():
					trig = 1
					break
				A[j][k] = min(P - B)
			if trig == 1:
				pk += 1
				A = [[0 for j in range(n)] for k in range(m)]
				break
		else:
			break
	print(max(P))
	for j in A:
		for k in j:
			print(k, end=' ')
		print()


for i in range(0, int(input())):
	(n, m) = map(int, input().split())
	if n >= 3 and m >= 3:
		print(4)
		l1 = []
		l2 = []
		y = 1
		for i in range(0, n):
			x = y
			for j in range(0, m):
				if i % 2 == 0:
					if j % 2 == 0 and j != 0:
						x += 1
					x = max(x % 5, 1)
					l2.append(x)
					if j == 1:
						y = max((x + 1) % 5, 1)
				else:
					l2.append(x)
					if j % 2 == 0:
						x += 1
					x = max(x % 5, 1)
					if j == 1:
						y = max((x + 1) % 5, 1)
			l1.append(l2)
			l2 = []
		for item in l1:
			print(' '.join((str(x) for x in item)))
	elif n == 1:
		if m <= 2:
			print(1)
			for i in range(0, m):
				print(1, end=' ')
			print('')
		else:
			print(2)
			x = 1
			for i in range(0, m):
				if i % 2 == 0 and i != 0:
					x += 1
					x = max(x % 3, 1)
				print(x, end=' ')
			print('')
	elif m == 1:
		if n <= 2:
			print(1)
			for i in range(0, n):
				print(1)
		else:
			print(2)
			x = 1
			for i in range(0, n):
				if i % 2 == 0 and i != 0:
					x += 1
					x = max(x % 3, 1)
				print(x)
	elif m == 2:
		if n == 2:
			print(2)
			print(1, 1)
			print(2, 2)
		else:
			print(3)
			x = 1
			for i in range(0, n):
				print(x, x)
				x += 1
				x = max(x % 4, 1)
	elif n == 2:
		print(3)
		x = 1
		for i in range(0, m):
			if i % 2 == 0 and i != 0:
				x += 1
				x = max(x % 4, 1)
			print(x, end=' ')
		print('')
		x = 2
		for i in range(0, m):
			print(x, end=' ')
			if i % 2 == 0:
				x += 1
				x = max(x % 4, 1)
		print('')


t = int(input())
while t:
	(n, m) = map(int, input().split(' '))
	if n == 1 and m == 1:
		print('1\n1')
	elif n == 1 and m > 1:
		k = 1
		arr = [0] * m
		arr[0] = 1
		arr[1] = 1
		for i in range(2, m):
			if arr[i - 2] == 1:
				arr[i] = 2
				k = 2
			elif arr[i - 2] == 2:
				arr[i] = 1
		print(k)
		for i in range(0, m):
			print(arr[i], end=' ')
		print('\n')
	elif m == 1 and n > 1:
		arr = [0] * n
		k = 1
		arr[0] = 1
		arr[1] = 1
		for i in range(2, n):
			if arr[i - 2] == 1:
				arr[i] = 2
				k = 2
			elif arr[i - 2] == 2:
				arr[i] = 1
		print(k)
		for i in range(0, n):
			print(arr[i])
	elif n == 2 and m == 2:
		print('2\n1 1\n2 2')
	elif n == 2 and m > 2:
		print('3')
		arr = [[0] * m for i in range(n)]
		arr[0][0] = 1
		arr[0][1] = 1
		arr[0][2] = 2
		arr[1][0] = 2
		arr[1][1] = 3
		arr[1][2] = 3
		for i in range(0, n):
			for j in range(3, m):
				if arr[i][j - 2] == 1:
					arr[i][j] = 2
				elif arr[i][j - 2] == 2:
					arr[i][j] = 3
				elif arr[i][j - 2] == 3:
					arr[i][j] = 1
		for i in range(0, n):
			for j in range(0, m):
				print(arr[i][j], end=' ')
			print('')
	elif m == 2 and n > 2:
		print('3')
		arr = [[0] * m for i in range(n)]
		arr[0][0] = 1
		arr[1][0] = 1
		arr[2][0] = 2
		arr[0][1] = 2
		arr[1][1] = 3
		arr[2][1] = 3
		for j in range(0, m):
			for i in range(3, n):
				if arr[i - 2][j] == 1:
					arr[i][j] = 2
				elif arr[i - 2][j] == 2:
					arr[i][j] = 3
				elif arr[i - 2][j] == 3:
					arr[i][j] = 1
		for i in range(0, n):
			for j in range(0, m):
				print(arr[i][j], end=' ')
			print('')
	elif n >= 3 and m >= 3:
		print('4')
		arr = [[0] * m for i in range(n)]
		count = 0
		for i in range(0, n, 2):
			if count % 2 == 0:
				arr[i][0] = 1
				arr[i][1] = 1
				for j in range(2, m):
					if arr[i][j - 2] == 1:
						arr[i][j] = 2
					elif arr[i][j - 2] == 2:
						arr[i][j] = 1
			else:
				arr[i][0] = 2
				arr[i][1] = 2
				for j in range(2, m):
					if arr[i][j - 2] == 1:
						arr[i][j] = 2
					elif arr[i][j - 2] == 2:
						arr[i][j] = 1
			count += 1
		count = 0
		for i in range(1, n, 2):
			if count % 2 == 0:
				arr[i][0] = 3
				arr[i][1] = 3
				for j in range(2, m):
					if arr[i][j - 2] == 3:
						arr[i][j] = 4
					elif arr[i][j - 2] == 4:
						arr[i][j] = 3
			else:
				arr[i][0] = 4
				arr[i][1] = 4
				for j in range(2, m):
					if arr[i][j - 2] == 3:
						arr[i][j] = 4
					elif arr[i][j - 2] == 4:
						arr[i][j] = 3
			count += 1
		for i in range(0, n):
			for j in range(0, m):
				print(arr[i][j], end=' ')
			print('')
	t -= 1


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	(a, b) = (M // 4, M % 4)
	(c, d) = (M // 3, M % 3)
	(strdn1, strdn2, ans) = ('1 1 2 2 ', '1 2 3 ', '')
	if N == 1 and M == 1:
		print(1, 1, sep='\n')
	elif N == 1:
		if M == 2:
			print(1)
		else:
			print(2)
		for i in range(1, a + 1):
			ans = ans + strdn1
		if b != 0:
			ans = ans + strdn1[:2 * b - 1]
		print(ans)
	elif M == 1:
		if N == 2:
			print(1)
		else:
			print(2)
		for i in range(1, N + 1):
			if i % 4 == 1 or i % 4 == 2:
				print(1)
			else:
				print(2)
	elif N == 2 and M == 2:
		print('2', '1 1', '2 2', sep='\n')
	elif N == 2:
		print(3)
		for i in range(1, c + 1):
			ans = ans + strdn2
		if d != 0:
			ans = ans + strdn2[:2 * d - 1]
		print(ans)
		print(ans)
	elif M == 2:
		print(3)
		for i in range(1, N + 1):
			if i % 3 == 0:
				print('3 3')
			else:
				print(str(i % 3) + ' ' + str(i % 3))
	else:
		print(4)
		(str1, str2) = ('1 2 3 4 ', '3 4 1 2 ')
		for i in range(1, N + 1):
			ans = ''
			if i % 4 == 1 or i % 4 == 2:
				for i in range(1, a + 1):
					ans = ans + str1
				if b != 0:
					ans = ans + str1[:2 * b - 1]
				print(ans)
			else:
				for i in range(1, a + 1):
					ans = ans + str2
				if b != 0:
					ans = ans + str2[:2 * b - 1]
				print(ans)


t = int(input())
for _ in range(t):
	(m, n) = [int(d) for d in input().split()]
	if m == 1:
		arr = []
		if n % 4 == 0:
			print(2)
			arr = [[1, 1, 2, 2] * (n // 4)]
		elif n % 4 == 1:
			if n == 1:
				print(1)
				arr = [[1]]
			else:
				print(2)
				arr = [[1, 1, 2, 2] * (n // 4) + [1]]
		elif n % 4 == 2:
			if n == 2:
				print(1)
				arr = [[1, 1]]
			else:
				print(2)
				arr = [[1, 1, 2, 2] * (n // 4) + [1, 1]]
		elif n % 4 == 3:
			print(2)
			arr = [[1, 1, 2, 2] * (n // 4) + [1, 1, 2]]
	elif m == 2:
		if n % 3 == 0:
			print(3)
			a1 = [1, 2, 3] * (n // 3)
			arr = [a1, a1]
		elif n % 3 == 1:
			if n == 1:
				print(1)
				arr = [[1], [1]]
			else:
				print(3)
				a1 = [1, 2, 3] * (n // 3) + [1]
				arr = [a1, a1]
		elif n % 3 == 2:
			if n == 2:
				print(2)
				arr = [[1, 2], [1, 2]]
			else:
				print(3)
				a1 = [1, 2, 3] * (n // 3) + [1, 2]
				arr = [a1, a1]
	elif m == 3:
		if n == 1:
			print(2)
			arr = [[1], [1], [2]]
		elif n == 2:
			print(3)
			arr = [[1, 1], [2, 2], [3, 3]]
		elif n == 3:
			print(4)
			arr = [[1, 3, 4], [4, 2, 1], [4, 2, 1]]
		elif n == 4:
			print(4)
			arr = [[1, 3, 4, 2], [4, 2, 1, 3], [4, 2, 1, 3]]
		elif n % 4 == 0:
			print(4)
			a1 = [1, 3, 4, 2] * (n // 4)
			a2 = [4, 2, 1, 3] * (n // 4)
			arr = [a1, a2, a2]
		elif n % 4 == 1:
			print(4)
			a1 = [1, 3, 4, 2] * (n // 4) + [1]
			a2 = [4, 2, 1, 3] * (n // 4) + [4]
			arr = [a1, a2, a2]
		elif n % 4 == 2:
			print(4)
			a1 = [1, 3, 4, 2] * (n // 4) + [1, 3]
			a2 = [4, 2, 1, 3] * (n // 4) + [4, 2]
			arr = [a1, a2, a2]
		elif n % 4 == 3:
			print(4)
			a1 = [1, 3, 4, 2] * (n // 4) + [1, 3, 4]
			a2 = [4, 2, 1, 3] * (n // 4) + [4, 2, 1]
			arr = [a1, a2, a2]
	elif n == 1:
		print(2)
		a1 = [1, 3, 4, 2] * (n // 4) + [1]
		a2 = [4, 2, 1, 3] * (n // 4) + [2]
		arr = []
		i = 0
		j = 0
		c = 0
		c1 = 0
		for i in range(m):
			if j == 0 and c < 3:
				arr.append(a1)
				c = c + 1
				if c == 2:
					j = 1
					c = 0
			else:
				arr.append(a2)
				c1 = c1 + 1
				if c1 == 2:
					j = 0
					c1 = 0
	elif n == 2:
		print(3)
		arr = []
		a1 = [1, 1]
		a2 = [2, 2]
		a3 = [3, 3]
		if m % 3 == 1:
			arr = [a1, a2, a3] * (m // 3) + [a1]
		elif m % 3 == 2:
			arr = [a1, a2, a3] * (m // 3) + [a1, a2]
		elif m % 3 == 0:
			arr = [a1, a2, a3] * (m // 3)
	else:
		print(4)
		if n % 4 == 0:
			a1 = [1, 3, 4, 2] * (n // 4)
			a2 = [4, 2, 1, 3] * (n // 4)
			arr = []
			i = 0
			j = 0
			c = 0
			c1 = 0
			for i in range(m):
				if j == 0 and c < 3:
					arr.append(a1)
					c = c + 1
					if c == 2:
						j = 1
						c = 0
				else:
					arr.append(a2)
					c1 = c1 + 1
					if c1 == 2:
						j = 0
						c1 = 0
		elif n % 4 == 1:
			a1 = [1, 3, 4, 2] * (n // 4) + [1]
			a2 = [4, 2, 1, 3] * (n // 4) + [4]
			arr = []
			i = 0
			j = 0
			c = 0
			c1 = 0
			for i in range(m):
				if j == 0 and c < 3:
					arr.append(a1)
					c = c + 1
					if c == 2:
						j = 1
						c = 0
				else:
					arr.append(a2)
					c1 = c1 + 1
					if c1 == 2:
						j = 0
						c1 = 0
		elif n % 4 == 2:
			a1 = [1, 3, 4, 2] * (n // 4) + [1, 3]
			a2 = [4, 2, 1, 3] * (n // 4) + [4, 2]
			arr = []
			i = 0
			j = 0
			c = 0
			c1 = 0
			for i in range(m):
				if j == 0 and c < 3:
					arr.append(a1)
					c = c + 1
					if c == 2:
						j = 1
						c = 0
				else:
					arr.append(a2)
					c1 = c1 + 1
					if c1 == 2:
						j = 0
						c1 = 0
		elif n % 4 == 3:
			a1 = [1, 3, 4, 2] * (n // 4) + [1, 3, 4]
			a2 = [4, 2, 1, 3] * (n // 4) + [4, 2, 1]
			arr = []
			i = 0
			j = 0
			c = 0
			c1 = 0
			for i in range(m):
				if j == 0 and c < 3:
					arr.append(a1)
					c = c + 1
					if c == 2:
						j = 1
						c = 0
				else:
					arr.append(a2)
					c1 = c1 + 1
					if c1 == 2:
						j = 0
						c1 = 0
	for i in range(m):
		for j in range(n):
			print(arr[i][j], end=' ')
		print()


n = int(input())
for i in range(0, n):
	(r, c) = map(int, input().split())
	if r == 1 and c == 1:
		print(1)
		print(1)
	elif r == 1 and c > 1:
		l = [1, 1, 2, 2]
		if c == 2:
			print(1)
		else:
			print(2)
		for i in range(c):
			print(l[i % 4], end=' ')
		print()
	elif c == 1 and r > 1:
		l = [1, 1, 2, 2]
		if r == 2:
			print(1)
		else:
			print(2)
		for i in range(r):
			print(l[i % 4])
	elif c == 2 and r > 1:
		l = [1, 2, 3]
		if r == 2:
			print(2)
		elif r > 2:
			print(3)
		for i in range(r):
			print(l[i % 3], l[i % 3])
	elif r == 2 and c > 2:
		print(3)
		l = [1, 2, 3]
		for i in range(0, c):
			print(l[i % 3], end=' ')
		print()
		for i in range(0, c):
			print(l[i % 3], end=' ')
		print()
	elif r > 2 and c > 2:
		print(4)
		l = [[1, 1, 3, 3], [2, 2, 4, 4], [3, 3, 1, 1], [4, 4, 2, 2]]
		for i in range(0, r):
			for j in range(0, c):
				print(l[i % 4][j % 4], end=' ')
			print()


t = int(input())
while t > 0:
	x = input()
	(n, m) = x.split(' ')
	n = int(n)
	m = int(m)
	if n == 1 and m == 2:
		print(1)
		print(1, 1)
	elif n == 2 and m == 1:
		print(1)
		print(1)
		print(1)
	elif m == 1 and n == 1:
		print(1)
		print(1)
	elif n == 1 and m == 1:
		print(1)
		print(1)
	elif n == 2 and m == 2:
		print(2)
		print(1, 1)
		print(2, 2)
	elif m >= n:
		if n == 1:
			print(2)
			count = 1
			for i in range(int(m / 2)):
				if count == 1:
					(print(1, 1, end=' '),)
					count = count + 1
				else:
					(print(2, 2, end=' '),)
					count = count - 1
			if m % 2 != 0:
				if count == 1:
					print(1)
				else:
					print(2)
		elif n == 2:
			print(3)
			count = 1
			for j in range(n):
				l = j + 1
				if l > 3:
					l = l % 3
				if l == 1:
					for i in range(int(m / 2)):
						print(l, l, end=' ')
						l = l + 1
						if l > 3:
							l = l % 3
					if m % 2 != 0:
						print(l, end=' ')
					print('')
				elif l == 2:
					print(l, end=' ')
					l = l + 1
					if l > 3:
						l = l % 3
					if m % 2 == 0:
						m2 = m - 2
					else:
						m2 = m
					for i in range(int(m2 / 2)):
						print(l, l, end=' ')
						l = l + 1
						if l > 3:
							l = l % 3
					if (m2 - 1) % 2 != 0:
						print(l, end=' ')
					print('')
		else:
			print(4)
			count = 1
			list1 = []
			for j in range(n):
				l = j + 1
				count = 1
				if j == 0:
					for i in range(int(m / 2)):
						if count == 1:
							print(l, l, end=' ')
							list1.append(l)
							list1.append(l)
							count = count + 1
							l = l + 1
							if l > 4:
								l = l % 4
						else:
							print(l, l, end=' ')
							list1.append(l)
							list1.append(l)
							count = count - 1
							l = l + 1
							if l > 4:
								l = l % 4
					if m % 2 != 0:
						list1.append(l)
						print(l, end=' ')
					print('')
				elif j % 2 != 0:
					list1[0] = list1[0] + 1
					l = list1[0]
					if list1[0] > 4:
						list1[0] = list1[0] % 4
					if l > 4:
						l = l % 4
					print(l, end=' ')
					l = l + 1
					if l > 4:
						l = l % 4
					if (m - 1) % 2 == 0:
						m2 = m - 1
					else:
						m2 = m - 1
					for i in range(int(m2 / 2)):
						print(l, l, end=' ')
						l = l + 1
						if l > 4:
							l = l % 4
					if m2 % 2 != 0:
						print(l, end=' ')
					print('')
				else:
					list1[0] = list1[0] + 2
					l = list1[0]
					if list1[1] > 4:
						list1[0] = list1[0] % 4
					if l > 4:
						l = l % 4
					for i in range(int(m / 2)):
						print(l, l, end=' ')
						l = l + 1
						if l > 4:
							l = l % 4
					if m % 2 != 0:
						print(l, end=' ')
					print('')
	elif m == 1:
		print(2)
		count = 1
		for i in range(int(n / 2)):
			if count == 1:
				print(1)
				print(1)
				count = count + 1
			else:
				print(2)
				print(2)
				count = count - 1
		if n % 2 != 0:
			if count == 1:
				print(1)
			else:
				print(2)
	elif m == 2:
		print(3)
		count = 1
		b1 = 1
		b2 = 2
		for j in range(n):
			print(b1, b2)
			if j % 2 == 0:
				b1 = b1
				b2 = b2 + 1
			else:
				b1 = b1 + 1
				b2 = b2
			if b1 > 3:
				b1 = b1 % 3
			if b2 > 3:
				b2 = b2 % 3
	else:
		print(4)
		count = 1
		list1 = []
		for j in range(n):
			l = j + 1
			count = 1
			if j == 0:
				for i in range(int(m / 2)):
					if count == 1:
						print(l, l, end=' ')
						list1.append(l)
						list1.append(l)
						count = count + 1
						l = l + 1
						if l > 4:
							l = l % 4
					else:
						print(l, l, end=' ')
						list1.append(l)
						list1.append(l)
						count = count - 1
						l = l + 1
						if l > 4:
							l = l % 4
				if m % 2 != 0:
					list1.append(l)
					print(l, end=' ')
				print('')
			elif j % 2 != 0:
				list1[0] = list1[0] + 1
				l = list1[0]
				if list1[0] > 4:
					list1[0] = list1[0] % 4
				if l > 4:
					l = l % 4
				print(l, end=' ')
				l = l + 1
				if l > 4:
					l = l % 4
				if (m - 1) % 2 == 0:
					m2 = m - 1
				else:
					m2 = m - 1
				for i in range(int(m2 / 2)):
					print(l, l, end=' ')
					l = l + 1
					if l > 4:
						l = l % 4
				if m2 % 2 != 0:
					print(l, end=' ')
				print('')
			else:
				list1[0] = list1[0] + 2
				l = list1[0]
				if list1[1] > 4:
					list1[0] = list1[0] % 4
				if l > 4:
					l = l % 4
				for i in range(int(m / 2)):
					print(l, l, end=' ')
					l = l + 1
					if l > 4:
						l = l % 4
				if m % 2 != 0:
					print(l, end=' ')
				print('')
	t = t - 1


testcase = int(input())
for i in range(testcase):
	(N, M) = list(map(int, input().split()))
	if N == 1 and M == 1:
		print('1')
		print('1')
	elif N == 1:
		if M == 2:
			print('1')
			print('1 1')
		else:
			seq = ['1', '1', '2', '2']
			print('2')
			ans = []
			for i in range(M):
				ans.append(seq[i % 4])
			print(' '.join(ans))
	elif N == 2:
		if M == 1:
			print('1')
			print('1')
			print('1')
		elif M == 2:
			print('2')
			print('1 2')
			print('1 2')
		else:
			seq = [['1', '1', '2', '3', '3', '2'], ['3', '3', '2', '1', '1', '2']]
			ans = []
			print('3')
			for j in range(N):
				temp = []
				for k in range(M):
					temp.append(seq[j][k % 6])
				ans.append(temp)
			for i in ans:
				print(' '.join(i))
	elif N == 3:
		if M == 1:
			print('2')
			print('1')
			print('1')
			print('2')
		elif M == 2:
			print('3')
			print('1 1')
			print('3 3')
			print('2 2')
		else:
			seq = [['1', '1', '2', '2'], ['3', '3', '4', '4'], ['2', '2', '1', '1']]
			ans = []
			print('4')
			for j in range(N):
				temp = []
				for k in range(M):
					temp.append(seq[j][k % 4])
				ans.append(temp)
			for i in ans:
				print(' '.join(i))
	elif N >= 4:
		if M == 1:
			print('2')
			seq = ['1', '1', '2', '2']
			for j in range(N):
				print(seq[j % 4])
		elif M == 2:
			print('3')
			seq = [['1', '2'], ['1', '2'], ['3', '3'], ['2', '1'], ['2', '1'], ['3', '3']]
			for i in range(N):
				for j in range(M - 1):
					print(seq[i % 6][j] + ' ' + seq[i % 6][j + 1])
		else:
			seq = [['1', '1', '2', '2'], ['3', '3', '4', '4'], ['2', '2', '1', '1'], ['4', '4', '3', '3']]
			print('4')
			ans = []
			for j in range(N):
				temp = []
				for k in range(M):
					temp.append(seq[j % 4][k % 4])
				ans.append(temp)
			for i in ans:
				print(' '.join(i))