Rahul and Tina are looking forward to starting their new year at college. As they enter their new classroom, they observe the seats of students are arranged in a $n \times m$ grid. The seat in row $r$ and column $c$ is denoted by $(r, c)$, and the distance between two seats $(a,b)$ and $(c,d)$ is $|a-c| + |b-d|$.

As the class president, Tina has access to exactly $k$ buckets of pink paint. The following process occurs.

First, Tina chooses exactly $k$ seats in the classroom to paint with pink paint. One bucket of paint can paint exactly one seat.

After Tina has painted $k$ seats in the previous step, Rahul chooses where he sits. He will not choose a seat that has been painted pink due to his hatred of the colour pink.

After Rahul has chosen his seat, Tina chooses a seat for herself. She can choose any of the seats, painted or not, other than the one chosen by Rahul.

Rahul wants to choose a seat such that he sits as close to Tina as possible. However, Tina wants to sit as far away from Rahul as possible due to some complicated relationship history that we couldn't fit into the statement!

Now, Rahul wonders for $k = 0, 1, \dots, n \cdot m - 1$, if Tina has $k$ buckets of paint, how close can Rahul sit to Tina, if both Rahul and Tina are aware of each other's intentions and they both act as strategically as possible? Please help satisfy Rahul's curiosity!


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $m$ ($2 \leq n \cdot m \leq 10^5$) — the number of rows and columns of seats in the classroom.

The sum of $n \cdot m$ across all test cases does not exceed $10^5$.


-----Output-----

For each test case, output $n \cdot m$ ordered integers — the distance between Rahul and Tina if both of them act optimally for every $k \in [0, n \cdot m - 1]$.


-----Examples-----

Input
2
4 3
1 2
Output
3 3 4 4 4 4 4 4 5 5 5 5 
1 1


-----Note-----

One possible sequence of choices for the first testcase where Tina has $k=3$ buckets of paints is as follows.

Tina paints the seats at positions $(1, 2)$, $(2, 2)$, $(3, 2)$ with pink paint. Rahul chooses the seat at $(3, 1)$ after which Tina chooses to sit at $(1, 3)$.

Therefore, the distance between Tina and Rahul is $|3-1| + |1-3| = 4$, and we can prove that this is indeed the minimum possible distance under the given constraints. There may be other choices of seats which lead to the same answer as well.

For $k=0$ in the first test case, Rahul can decide to sit at $(2, 2)$ and Tina can decide to sit at $(4, 3)$ so the distance between them would be $|2 - 4| + |2 - 3| = 3$.

Below are pictorial representations of the $k=3$ and $k=0$ cases for the first test case.

A possible seating arrangement for $k=3$.

A possible seating arrangement for $k=0$.

Difficulty: EASY
Tags: Sorting

Game theory

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	d = [max(i, n - 1 - i) + max(j, m - 1 - j) for j in range(m) for i in range(n)]
	d.sort()
	print(' '.join(map(str, d)))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = n + m - 2
	mas = []
	for i in range(0, m // 2):
		mas.append(d)
		d -= 1
	if m > 1:
		mas = mas * 2
	if m % 2 == 1:
		mas.append(d)
	for i in range(1, n // 2):
		for j in range(0, m):
			mas.append(mas[j] - i)
	if n > 1:
		mas = mas * 2
		if n % 2 == 1:
			for j in range(0, m):
				mas.append(mas[j] - n // 2)
	mas.sort()
	print(' '.join([str(i) for i in mas]))


import sys
input = sys.stdin.readline
repeat = int(input())
for _ in range(repeat):
	(n, m) = map(int, input().split())
	mini = m // 2 + n // 2
	maxi = mini + (m - 1) // 2 + (n - 1) // 2
	limit = min((n + 1) // 2, (m + 1) // 2)
	length = maxi - mini + 1
	number = [limit * 4] * length
	i = 0
	d = limit - 1
	while True:
		if d <= 0:
			break
		number[i] -= d * 4
		number[length - i - 1] -= d * 4
		i += 1
		d -= 1
	if n % 2 == 1:
		for i in range((m + 1) // 2):
			number[i] -= 2
	if m % 2 == 1:
		for i in range((n + 1) // 2):
			number[i] -= 2
	if n % 2 == 1 and m % 2 == 1:
		number[0] += 1
	for i in range(length):
		for j in range(number[i]):
			print(mini + i, end=' ')
	print()


T = int(input())

def main(r, c):
	d = []
	for i in range(1, r + 1):
		for k in range(1, c + 1):
			d.append(max(abs(i - 1) + abs(k - 1), abs(i - 1) + abs(k - c), abs(i - r) + abs(k - 1), abs(i - r) + abs(k - c)))
	d.sort()
	output = ''
	for i in d:
		output += str(i) + ' '
	return output[:-1]

class case:

	def __init__(self, Line):
		temp = Line.split()
		self.rows = int(temp[0])
		self.col = int(temp[1])
cases = []
for i in range(T):
	line = input()
	cases.append(case(line))
for i in range(T):
	print(main(cases[i].rows, cases[i].col))


import math, re

def fastlist():
	return list(map(int, input().split()))

def fastint():
	return int(input())

def solve():
	(n, m) = fastlist()
	res = []
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if i >= n // 2 + 1 and j >= m // 2 + 1:
				res.append(i + j - 2)
			elif i < n // 2 + 1 and j >= m // 2 + 1:
				res.append(abs(n - i) + j - 1)
			elif i < n // 2 + 1 and j < m // 2 + 1:
				res.append(abs(n - i) + abs(m - j))
			else:
				res.append(i - 1 + abs(m - j))
	res.sort()
	return ' '.join(list(map(str, res)))
t = int(input())
for _ in range(t):
	print(solve())


def solve(n: int, m: int):
	ans = []
	for i in range(n):
		for j in range(m):
			ans.append(max(n - i - 1, i) + max(m - j - 1, j))
	ans.sort()
	print(' '.join(map(str, ans)))
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	solve(n, m)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
for t in range(int(input())):
	(n, m) = map(int, input().split())
	print(*sorted((max(x, n - 1 - x) + max(y, m - 1 - y) for x in range(n) for y in range(m))))


import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	(num_rows, num_cols) = [int(x) for x in input().split()]
	i_center = (num_rows - 1) / 2
	j_center = (num_cols - 1) / 2
	offset = i_center + j_center
	distances = [int(abs(i - i_center) + abs(j - j_center) + offset) for i in range(num_rows) for j in range(num_cols)]
	distances.sort()
	print(*distances)


size = int(input())
for i in range(size):
	str1 = input().split()
	n = int(str1[0])
	m = int(str1[1])
	output = []
	for i in range(n):
		x = max(abs(0 - i), abs(n - 1 - i))
		for j in range(m):
			y = max(abs(0 - j), abs(m - 1 - j))
			output += [x + y]
	out = sorted(output)
	print(' '.join(map(str, out)))


def read_input():
	t = int(input())
	test_cases = []
	for i in range(t):
		i_line = input().split(' ')
		test_case = [int(i_line[0]), int(i_line[1])]
		test_cases.append(test_case)
	return test_cases

def solve(test_case):
	(n, m) = (test_case[0], test_case[1])
	values_of_seats = []
	for i in range(n):
		for j in range(m):
			value = max(i, n - i - 1) + max(j, m - j - 1)
			values_of_seats.append(value)
	values_of_seats.sort()
	for k in range(n * m):
		print(values_of_seats[k], end=' ')
	print()

def main():
	test_cases = read_input()
	for test_case in test_cases:
		solve(test_case)
main()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	seats = []
	for i in range(n):
		for j in range(m):
			seats.append(max(i, n - 1 - i) + max(j, m - 1 - j))
	seats.sort()
	print(*seats)


nt = int(input())
ans = []

def soln(n, m):
	k = 0
	max_dist = []
	ans = []
	for x in range(n):
		for y in range(m):
			max_dist.append(max(x, n - x - 1) + max(y, m - y - 1))
	max_dist.sort()
	return max_dist
for x in range(nt):
	inp = list(map(int, input().split()))
	(n, m) = (inp[0], inp[1])
	ans.append(soln(n, m))
for a in ans:
	for x in a:
		print(x, end=' ')
	print()


def problemB(n, m):
	distance = []
	for i in range(n):
		for j in range(m):
			distance.append(max(i + j, i + abs(j - m + 1), abs(i - n + 1) + j, abs(i - n + 1) + abs(j - m + 1)))
	distance.sort()
	return ' '.join([str(num) for num in distance])
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	print(problemB(n, m))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	print(*sorted((max(x, n - 1 - x) + max(y, m - 1 - y) for x in range(n) for y in range(m))))


import sys
from math import ceil
ls = []
for l in sys.stdin:
	lst = l.rstrip('\n')
	if len(lst) > 0:
		ls.append(lst)
for l in ls:
	sys.stderr.write(l + '\n')
sys.stderr.write('-- output --\n')

def d(u, v):
	return abs(u[0] - v[0]) + abs(u[1] - v[1])

def opp(i, n):
	return n - 1 if i < n // 2 else 0

def coin_opp(i, j, n, m):
	return (opp(i, n), opp(j, m))

def solve(n, m):
	res = []
	for i in range(n):
		for j in range(m):
			res.append(d((i, j), coin_opp(i, j, n, m)))
	return sorted(res)
for l in ls[1:]:
	(n, m) = [int(w) for w in l.split(' ')]
	print(*solve(n, m))


from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
from re import search
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
sbstr = lambda a, s: search('.*'.join(a), s)

def solve(__=1):
	for _ in range(__):
		(n, m) = li()
		d = []
		for i in range(n):
			for j in range(m):
				d.append(max(i + j, i + (m - 1 - j), n - 1 - i + j, m + n - i - j - 2))
		d.sort()
		print(*d)
solve(inp())


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	print(*sorted([max(i, n - i - 1) + max(j, m - j - 1) for i in range(n) for j in range(m)]))


t = int(input())
nt = []
mt = []
for i in range(t):
	temp = input().split()
	nt.append(int(temp[0]))
	mt.append(int(temp[1]))
for i in range(t):
	n = nt[i]
	m = mt[i]
	tab = []
	for a in range(n):
		for b in range(m):
			if a >= n / 2:
				c = 0
			else:
				c = n - 1
			if b >= m / 2:
				d = 0
			else:
				d = m - 1
			tab.append(abs(a - c) + abs(b - d))
	tab.sort(reverse=True)
	for k in range(n * m - 1, -1, -1):
		print(tab[k], end=' ')
	print('')


import math
n = int(input())
for _ in range(n):
	(n, m) = map(int, input().split())
	dist = m // 2 + n // 2
	(m, n) = (max(m, n), min(m, n))
	med_n = (n - 1) / 2
	med_m = (m - 1) / 2
	l = []
	l += [dist] * ((m % 2 or 2) * (n % 2 or 2))
	for i in range(1, dist + n % 2 + m % 2):
		count = 0
		for j in range(i + 1):
			if med_n - j < 0:
				break
			if med_m - i + j >= 0:
				count += 4 - 2 * (j == i) * (m % 2) - 2 * (j == 0) * (n % 2)
		l += [dist + i] * count
	print(*l)


from collections import defaultdict
import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = defaultdict(lambda : 0)
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			st = max(n - i + m - j, i - 1 + j - 1, i - 1 + m - j, n - i + j - 1)
			d[st] += 1
	ans = []
	for i in d.keys():
		ans += [i] * d[i]
	ans.sort()
	print(*ans)


def solve():
	(n, m) = list(map(int, list(input().split())))
	x = []
	for i in range(n):
		for j in range(m):
			x.append(max(i, n - i - 1) + max(j, m - j - 1))
	x.sort()
	print(*x)
q = int(input())
for i in range(q):
	solve()


T = int(input())
for t in range(T):
	(n, m) = list(map(int, input().split()))
	l = []
	for i in range(n):
		for j in range(m):
			l.append(max(i, n - 1 - i) + max(j, m - j - 1))
	print(*sorted(l))


I = lambda : [int(x) for x in input().split()]
for t in range(int(input())):
	(n, m) = I()
	list = [max(x, n - 1 - x) + max(y, m - 1 - y) for x in range(n) for y in range(m)]
	list.sort()
	print(*list)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = []
	for i in range(n):
		for j in range(m):
			lst.append(max(i, n - 1 - i) + max(j, m - 1 - j))
	lst = sorted(lst)
	print(*lst)


t = int(input())
for i in range(t):
	(m, n) = map(lambda x: int(x), input().split())
	arr = []
	for i in range(m):
		for j in range(n):
			a = i + j
			b = i + n - 1 - j
			c = m - 1 - i + j
			d = m - 1 - i + n - 1 - j
			arr.append(max(a, b, c, d))
	print(' '.join(map(lambda x: str(x), sorted(arr))))


import math
from collections import *
import math

def solve():
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		for j in range(m):
			a.append(max(i, n - i - 1) + max(j, m - j - 1))
	a.sort()
	print(*a)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	dis = []
	for i in range(n):
		for j in range(m):
			x = max(j, m - j - 1)
			y = max(i, n - i - 1)
			dist = x + y
			dis.append(dist)
	dis.sort()
	print(*dis)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		for j in range(m):
			dist = max(i, n - 1 - i) + max(j, m - 1 - j)
			a.append(dist)
	a.sort()
	print(*a)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	k = []
	for i in range(n):
		for j in range(m):
			a1 = i + j
			a2 = i + m - 1 - j
			a3 = j + n - 1 - i
			a4 = n - 1 - i + m - 1 - j
			k.append(max(a1, a2, a3, a4))
	k = sorted(k)
	k = [str(i) for i in k]
	print(' '.join(k))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = []
	for i in range(m):
		for j in range(n):
			ans.append(max(i, m - i - 1) + max(j, n - j - 1))
	ans.sort()
	print(*ans)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	(m, n, mm, nn) = (max(a), min(a), 1, 1)
	(r, res) = (m * n // 2, [])
	for i in range(r):
		if nn == n + 1:
			nn = 1
			mm += 1
		f = m - mm + n - nn
		s = m - mm + nn - 1
		res += [max(f, s)]
		nn += 1
	res = 2 * res
	p = m * n
	if p % 2:
		f = n - (n + 1) // 2 + m - (m + 1) // 2
		res += [f]
	res = sorted(res)
	print(*res, sep=' ')


t = int(input())
while t:
	t -= 1
	(n, m) = [int(i) for i in input().split()]
	v = []
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			dist = max(i - 1, n - i) + max(j - 1, m - j)
			v.append(dist)
	v.sort()
	print(*v)


import sys
input = sys.stdin.readline
t = int(input().strip())
for _ in range(t):
	(n, m) = map(int, input().split())
	lst = []
	for i in range(n):
		for j in range(m):
			lst.append(max(abs(i) + abs(j), abs(i) + abs(m - j - 1), abs(j) + abs(n - i - 1), abs(n - i - 1) + abs(m - j - 1)))
	print(*sorted(lst))


def solve(n, m):
	res = []
	for i in range(n):
		for j in range(m):
			dists = [i + j, i + (m - j - 1), n - i - 1 + j, n - i - 1 + (m - j - 1)]
			res.append(max(dists))
	print(*sorted(res))
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	solve(n, m)


for l in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		for j in range(m):
			a.append(max(i, n - i - 1) + max(j, m - j - 1))
	print(*sorted(a))


import math

def main_function():
	test_cases = range(int(input()))
	for test_case in test_cases:
		(n, m) = [int(i) for i in input().split()]
		map = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				map[i][j] = max(abs(i) + abs(j), abs(n - i - 1) + abs(j), abs(n - i - 1) + abs(m - j - 1), abs(i) + abs(m - j - 1))
		real_one = []
		for i in range(n):
			for j in range(m):
				real_one.append(map[i][j])
		real_one.sort()
		print(' '.join([str(u) for u in real_one]))
main_function()


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	arr = []
	for i in range(1, (r + 1) // 2 + 1):
		for j in range(1, (c + 1) // 2 + 1):
			val = abs(r - i) + abs(c - j)
			factor = 4
			if j == (c + 1) // 2 and c % 2 != 0:
				factor = factor // 2
			if i == (r + 1) // 2 and r % 2 != 0:
				factor = factor // 2
			for k in range(factor):
				arr.append(val)
	arr.sort()
	for i in arr:
		print(i, end=' ')
	print()


t = int(input())
while t > 0:
	(n, m) = list(map(int, list(input().split())))
	x = []
	for i in range(n):
		for j in range(m):
			x.append(max(i, n - i - 1) + max(j, m - j - 1))
	x.sort()
	print(*x)
	t -= 1


def solve(n, m):
	corners = [[1, 1], [1, m], [n, 1], [n, m]]
	dist = []
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			maxDist = max([abs(ci - i) + abs(cj - j) for (ci, cj) in corners])
			dist.append(maxDist)
	dist.sort()
	print(' '.join(map(str, dist)))
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	solve(n, m)


from collections import Counter
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	l = []
	for i in range(N):
		for j in range(M):
			l.append(max(i, N - i - 1) + max(j, M - j - 1))
	print(*sorted(l))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = []
	for j in range(n):
		for k in range(m):
			a.append(max(j + k, j + m - 1 - k, n - 1 - j + k, n + m - 2 - j - k))
	a.sort()
	print(*a)


import math
t = int(input())
for _ in range(t):
	(rr, cc) = list(map(int, input().split()))
	x = rr
	y = cc
	r = math.ceil(rr / 2)
	c = math.ceil(cc / 2)
	lst = []
	i = 1
	j = 1
	while i < rr or j < cc:
		if i > r:
			x = 1
		else:
			x = rr
		if j > c:
			y = 1
		else:
			y = cc
		lst.append(abs(x - i) + abs(y - j))
		if j == cc:
			j = 1
			i += 1
		else:
			j += 1
	lst.append(max(lst))
	lst.sort()
	print(*lst)


from re import L
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def func():
	(r, c) = mul()
	req = []
	for i in range(r):
		for j in range(c):
			req.append(max(i, r - 1 - i) + max(j, c - 1 - j))
	req.sort()
	print(*req)
t = inp()
for i in range(t):
	func()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		for j in range(m):
			x = i + j
			x = max(x, n - 1 - i + m - 1 - j)
			x = max(x, i + m - 1 - j)
			x = max(x, n - 1 - i + j)
			l.append(x)
	l.sort()
	print(*l)


import math
mod = 10 ** 9 + 7

def findval(i, j, n, m):
	val1 = abs(i - 1) + abs(j - 1)
	val2 = abs(i - n) + j - 1
	val3 = abs(i - 1) + abs(j - m)
	val4 = abs(i - n) + abs(j - m)
	val = max({val1, val2, val3, val4})
	return val

def main():
	t = int(input())
	while t != 0:
		ans = []
		(n, m) = map(int, input().split())
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				val = findval(i, j, n, m)
				ans.append(val)
		ans.sort()
		for it in ans:
			print(it, end=' ')
		print()
		t -= 1
main()


import sys, bisect, math
from collections import deque, Counter
input = lambda : sys.stdin.readline().strip()
ceil = lambda x: math.ceil(x)
mod = 10 ** 9 + 7

def solve():
	(n, m) = map(int, input().split())
	a = []
	dist = lambda d1, d2: abs(d1[0] - d2[0]) + abs(d1[1] - d2[1])
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			ma = max(dist([i, j], [1, 1]), dist([i, j], [1, m]), dist([i, j], [n, 1]), dist([i, j], [n, m]))
			a.append(ma)
	a.sort()
	return ' '.join((str(x) for x in a))
t = 1
t = int(input())
for _ in range(t):
	print(solve())


for z in range(int(input())):
	arr = []
	(n, m) = map(int, input().split())
	for i in range(n):
		for j in range(m):
			max_d = max(i + j, i + (m - 1 - j), n - 1 - i + j, m + n - i - j - 2)
			arr.append(max_d)
	arr.sort()
	print(*arr)


def int_input():
	a = int(input())
	return a

def int_list_input():
	a = list(map(int, input().split()))
	return a

def solve():
	(n, m) = int_list_input()
	arr = []
	for i in range(n):
		for j in range(m):
			a = max(i + j, i + (m - j - 1), n - i - 1 + j, n - i - 1 + (m - j - 1))
			arr.append(a)
	arr.sort()
	for i in range(n * m):
		print(arr[i], end=' ')
	print()
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	l = [max(x, n - 1 - x) + max(y, m - 1 - y) for x in range(n) for y in range(m)]
	l.sort()
	for i in l:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [0 for i in range(n * m)]
	for i in range(n):
		for j in range(m):
			a[i * m + j] = max(i + j, i + m - j - 1, n - i + j - 1, n - i + m - j - 2)
	a.sort()
	print(*a)


no = int(input(''))
for i in range(no):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		for j in range(m):
			l.append(max(i, n - 1 - i) + max(j, m - 1 - j))
	l.sort()
	for p in range(n * m):
		print(l[p], end=' ')
	print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		for j in range(m):
			arr.append(max(i + j, m + n - i - j - 2, m + i - j - 1, n - i + j - 1))
	arr.sort()
	for i in arr:
		print(str(i), end=' ')
	print()


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	lis = []
	for y in range(n):
		for z in range(k):
			lis.append(max(n - 1 - y + k - 1 - z, y + z, y + k - 1 - z, n - 1 - y + z))
	lis.sort()
	for out in lis:
		print(out, end=' ')
	print('')


for i in range(0, int(input())):
	(n, m) = map(int, input().split())
	l = []
	for j in range(1, n + 1):
		for k in range(1, m + 1):
			l.append(max(abs(1 - k), abs(k - m)) + max(abs(1 - j), abs(n - j)))
	l.sort()
	print(*l, sep=' ')


import sys
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

def inp():
	return int(input())

def read_int_list():
	return list(map(int, input().split()))

def read_list():
	s = input()
	return list(s[:len(s) - 1])

def manhattan(x, y, a, b):
	return abs(x - a) + abs(y - b)

def solve(n, m):
	corners = [(0, 0), (0, m - 1), (n - 1, 0), (n - 1, m - 1)]
	d = []
	for x in range(n):
		for y in range(m):
			cd = []
			for c in corners:
				cd.append(manhattan(x, y, c[0], c[1]))
			d.append(max(cd))
	print(*sorted(d))
for _ in range(inp()):
	(n, m) = read_int_list()
	solve(n, m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			l.append(max(abs(n - i + m - j), abs(n - i + j - 1), abs(m - j + i - 1), abs(i + j - 2)))
	l.sort()
	print(*l)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	cnt = [0] * (n + m - 1)
	for i in range(n):
		for j in range(m):
			dist = max(i, n - i - 1) + max(j, m - j - 1)
			cnt[dist] += 1
	for i in range(n + m - 1):
		for j in range(cnt[i]):
			print(i, end=' ')
	print()


for t in range(int(input())):
	(n, m) = map(int, input().split())
	(x1, y1) = (0, 0)
	(x2, y2) = (n - 1, 0)
	(x3, y3) = (0, m - 1)
	(x4, y4) = (n - 1, m - 1)
	A = list()
	for i in range(n):
		for j in range(m):
			d1 = abs(i - x1) + abs(j - y1)
			d2 = abs(i - x2) + abs(j - y2)
			d3 = abs(i - x3) + abs(j - y3)
			d4 = abs(i - x4) + abs(j - y4)
			d = max(d1, d2, d3, d4)
			A.append(d)
	A.sort()
	print(*A)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	d = []
	for k in range(n):
		for j in range(m):
			d.append(max(abs(k - 1 + 1) + abs(j + 1 - 1), abs(k + 1 - 1) + abs(j + 1 - m), abs(k + 1 - n) + abs(j + 1 - 1), abs(k + 1 - n) + abs(j + 1 - m)))
	d.sort()
	print(*d)


for _ in range(int(input())):
	(n, m) = [int(item) for item in input().split()]
	ans = [0] * (m * n)
	ang = []
	for i in range(1, n + 1):
		for y in range(1, m + 1):
			ang.append(min([i, n + 1 - i]) + min([y, m + 1 - y]) - 1)
	ans[0] = n // 2 + m // 2
	ang.sort(reverse=True)
	tambah = 0
	for x in range(1, len(ang)):
		if ang[x] != ang[x - 1]:
			tambah += 1
		else:
			pass
		ans[x] = ans[0] + tambah
	print(*ans)


def solution(m, n):
	res = []
	visit = [[0] * n for _ in range(m)]
	(row, col) = ([], [])
	if m % 2 == 1:
		row.append(m // 2)
	else:
		row.append(m // 2)
		row.append(m // 2 - 1)
	if n % 2 == 1:
		col.append(n // 2)
	else:
		col.append(n // 2)
		col.append(n // 2 - 1)
	q = []
	for r in row:
		for c in col:
			q.append((r, c))
			visit[r][c] = 1
	while q:
		(r, c) = (q[0][0], q[0][1])
		dist = max(r, m - r - 1) + max(c, n - c - 1)
		res += [dist] * len(q)
		for _ in range(len(q)):
			(r, c) = q.pop(0)
			for (x, y) in [(r - 1, c), (r, c - 1), (r, c + 1), (r + 1, c)]:
				if 0 <= x < m and 0 <= y < n and (visit[x][y] == 0):
					visit[x][y] = 1
					q.append((x, y))
	return ' '.join([str(k) for k in res])
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(solution(n, m))


import sys

def solve(n, m):
	if n % 2 and m % 2:
		level = {(n // 2, m // 2)}
	elif n % 2 and (not m % 2):
		level = {(n // 2, cj) for cj in [m // 2 - 1, m // 2]}
	elif not n % 2 and m % 2:
		level = {(ci, m // 2) for ci in [n // 2 - 1, n // 2]}
	else:
		level = {(ci, cj) for ci in [n // 2 - 1, n // 2] for cj in [m // 2 - 1, m // 2]}
	visit = level.copy()
	(ci, cj) = list(level)[0]
	v = max((abs(pi - ci) + abs(pj - cj) for (pi, pj) in [(0, 0), (0, m - 1), (n - 1, 0), (n - 1, m - 1)]))
	res = [v] * len(level)
	while level:
		nextlevel = set()
		for (pi, pj) in level:
			for (ci, cj) in [(pi - 1, pj), (pi, pj - 1), (pi, pj + 1), (pi + 1, pj)]:
				if 0 <= ci < n and 0 <= cj < m and ((ci, cj) not in visit):
					visit.add((ci, cj))
					nextlevel.add((ci, cj))
		level = nextlevel
		res += [res[-1] + 1] * len(level)
	return res[:n * m]
input = sys.stdin.readline
t = int(input()[:-1])
for _ in range(t):
	(n, m) = [int(part) for part in input()[:-1].split()]
	for val in solve(n, m):
		print(val, end=' ')
	print('\n', end='')