Anas is playing an amazing game on a grid with $N$ rows and $M$ columns. The rows are numbered $1$ through $N$ from top to bottom and the columns are numbered $1$ through $M$ from left to right.
Anas wants to destroy this grid. To do that, he wants to send two heroes from the top left cell to the bottom right cell:
- The first hero visits cells in row-major order: $(1,1) \rightarrow (1,2) \rightarrow \ldots \rightarrow (1,M) \rightarrow (2,1) \rightarrow (2,2) \rightarrow \ldots \rightarrow (2,M) \rightarrow \ldots \rightarrow (N,M)$.
- The second hero visits cells in column-major order: $(1,1) \rightarrow (2,1) \rightarrow \ldots \rightarrow (N,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow \ldots \rightarrow (N,2) \rightarrow \ldots \rightarrow (N,M)$.
We know that each hero destroys the first cell he visits, rests in the next $K$ cells he visits without destroying them, then destroys the next cell he visits, rests in the next $K$ cells, destroys the next cell, and so on until he reaches (and rests in or destroys) the last cell he visits.
Anas does not know the value of $K$. Therefore, for each value of $K$ between $0$ and $N \cdot M - 1$ inclusive, he wants to calculate the number of cells that will be destroyed by at least one hero. Can you help him?

-----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 a single line containing $N \cdot M$ space-separated integers as described above.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N, M \le 1,000$
- the sum of $N \cdot M$ over all test cases does not exceed $2 \cdot 10^6$

-----Subtasks-----
Subtask #1 (30 points):
- $2 \le N, M \le 50$
- the sum of $N \cdot M$ over all test cases does not exceed $5,000$
Subtask #2 (70 points): original constraints

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

-----Example Output-----
6 4 3 3 2 1

-----Explanation-----
Example case 1:
- $K = 0$: All cells will be destroyed by the heroes.
- $K = 1$: The first hero will destroy the cells $[(1,1), (1,3), (2,2)]$, while the second one will destroy the cells $[(1,1), (1,2), (1,3)]$.
- $K = 2$: The first hero will destroy the cells $[(1,1), (2,1)]$, while the second one will destroy the cells $[(1,1), (2,2)]$.
- $K = 3$: The first hero will destroy the cells $[(1,1), (2,2)]$, while the second one will destroy the cells $[(1,1), (1,3)]$.
- $K = 4$: The first hero will destroy the cells $[(1,1), (2,3)]$ and the second one will also destroy the cells $[(1,1), (2,3)]$.
- $K = 5$ : The first hero will destroy the cell $(1,1)$ and the second one will also destroy the cell $(1,1)$.

Difficulty: interview

Starter code:

Solutions:
"""
Code chef problem DESTCELL, Destroy Cells
"""


def find_destroyed_cells(cell_advance, n, m, k):
 row = 1
 col = 1
 destroyed_cells = {(1, 1)}
 while True:
  row, col = cell_advance(row, col, n, m, k)
  if row <= n and col <= m:
   destroyed_cells.add((row, col))
  else:
   break
 return destroyed_cells


def cell_advance_hero1(row, col, n, m, k):
 return row + (col + k) // m, (col + k) % m + 1


def cell_advance_hero2(row, col, n, m, k):
 return (row + k) % n + 1, col + (row + k)//n


def main():
 t = int(input())
 for _ in range(t):
  n, m = [int(s) for s in input().split(' ')]
  counts = []
  for k in range(n*m):
   cells_h1 = find_destroyed_cells(cell_advance_hero1, n, m, k)
   cells_h2 = find_destroyed_cells(cell_advance_hero2, n, m, k)

   destroyed = len(cells_h1) + len(cells_h2) - len(cells_h1 & cells_h2)
   counts.append(destroyed)
  print(' '.join([str(c) for c in counts]))


main()


t = int(input())
while t > 0:
 ans = []
 n, m = list(map(int, input().split()))
 temp = []
 for k in range(0, n*m):
  myset1 = set()
  myset2 = set()
  if k == 0:
   ans.append(n*m)
  elif k == n*m - 1:
   ans.append(1)
  else:
   for j in range(1, m+1):
    i = j
    while i <= n*m:
     temp.append(i)
     i += m
   i = 1
   while i <= n*m:
    myset1.add(i)
    i = i + k + 1
   i = 0
   while i <= n*m-1:
    myset2.add(temp[i])
    i = i + k + 1
   current = list(myset1.union(myset2))
   ans.append(len(current))
 print(*ans)
 t -= 1


t = int(input(''))
for v in range(t):
 a = input('').split(' ')
 n = int(a[0])
 m = int(a[1])
 ans = [0]*(n*m)
 for k in range(0,n*m,1):
  su = 2*((n*m-1)//(k+1)+1)
  g = 0
  while(g<n*m):
   j = g%(m)
   i = g//m
   #print((j*n + i),g,k+1)
   if((j*n + i)%(k+1) == 0):
    su = su - 1
   #print(g,su)
   g = g + (k+1)
  print(su, end = ' ')
 print('')
      

t = int(input(''))
for v in range(t):
 a = input('').split(' ')
 n = int(a[0])
 m = int(a[1])
 ans = [0]*(n*m)
 for k in range(0,n*m,1):
  su = 2*((n*m-1)//(k+1)+1)
  g = 0
  while(g<n*m):
   j = g%(m)
   i = g//m
   #print((j*n + i),g,k+1)
   if((j*n + i)%(k+1) == 0):
    su = su - 1
   #print(g,su)
   g = g + (k+1)
  print(su, end = ' ')
 print('')
      

# cook your dish here
from math import ceil
for _ in range(int(input())):
 n,m=list(map(int,input().split()))
 l=[str(n*m)]
 #print(ceil(5.3))
 for i in range(1,n*m):
  c=2*ceil((n*m)/(i+1))
  #print(c,"sas",(n*m)/(i+1))
  for k in range(0,n*m,i+1):
   r=k%m
   q=k//m
   if((r*n+q)%(i+1)==0):
    c-=1
  l.append(str(c))
 print(" ".join(l))

# cook your dish here
def destroy_cells(N,M):
 print(N*M,end=' ')
 
 for k in range(1,N*M-1):
  row,col,i,j = 0,0,0,0
  positions = [(0,0)]
  
  while row < N or col < M:
   j = j+k+1
   if j >= M:
    row += j//M
   if row < N:
    j = j%M
    positions.append((row,j))
   
   i = i+k+1
   if i >= N:
    col += i//N
   if col < M:
    i = i%N
    positions.append((i,col))
    
  positions = set(positions)
  print(len(positions),end=' ')
 
 print(1)

test = int(input())
for i in range(test):
 (N,M) = (map(int,input().split()))
 destroy_cells(N,M)

t=int(input())
for tc in range(t):
 n,m=map(int,input().split())
 s=n*m
 x=[]
 y=[]
 z=[]
 a=[]
 print(n*m,end=" ")
 for i in range(1,n+1):
  for j in range(1,m+1):
   x.append([i,j])
 for j in range(1,m+1):
  for i in range(1,n+1):
   y.append([i,j])
 for k in range(1,m*n):
  a=[]
  z=[]
  for i in range(0,n*m,k+1):
   z.append(x[i])
  for j in range(0,n*m,k+1):
   z.append(y[j]) 
  for i in z:
   if i not in a:
    a.append(i) 
  print(len(a),end=" ")
 print()


t=int(input())
for tc in range(t):
 n,m=map(int,input().split())
 s=n*m
 x=[]
 y=[]
 z=[]
 a=[]
 print(n*m,end=" ")
 for i in range(1,n+1):
  for j in range(1,m+1):
   x.append([i,j])
 for j in range(1,m+1):
  for i in range(1,n+1):
   y.append([i,j])
 for k in range(1,m*n):
  a=[]
  z=[]
  for i in range(0,n*m,k+1):
   z.append(x[i])
  for j in range(0,n*m,k+1):
   z.append(y[j]) 
  for i in z:
   if i not in a:
    a.append(i) 
  print(len(a),end=" ")
 print()


# cook your dish here
t=int(input())
for i in range(t):
 n,m=map(int,input().split())
 for k in range(n*m):
  s=''
  t=''
  for i in range(n*m):
   s+='0'
  i=0
  while(i<len(s)):
   s=s[:i]+'1'+s[i+1:]
   i+=k+1
  i=0
  for i in range(n):
   while(i<len(s)):
    t+=s[i]
    i+=n 
  i=0
  while(i<len(t)):
   t=t[:i]+'1'+t[i+1:]
   i+=k+1
  print(t.count('1'),' ',end='')
    
 
   
   
     
  
    
  
  


for x in range(int(input())):
 n,m=map(int,input().split())
 y=n*m
 print(y,end=" ")
 for x in range(1,n*m):
  ans = 2*(1+ (n*m-1)//(x+1))
  mu=0
  while(mu<y):
   n1=mu//m
   m1=mu%m
   y2=m1*n+n1
   if(y2%(x+1)==0):
    ans-=1
   mu+=x+1
  print(ans,end=" ")
 print("")


for x in range(int(input())):
 n,m=map(int,input().split())
 y=n*m
 l=[]
 for x in range(n*m):
  p=x+1
  if(y%p==0):
   ans=2*(y//p)
  else:
   ans=2*((y//p)+1)
  mu=0
  while(mu<y):
   n1=mu//m
   m1=mu%m
   y2=m1*n+n1
   if(y2%(x+1)==0):
    ans-=1
   mu+=x+1
  print(ans,end=" ")
 print("")


for x in range(int(input())):
 n,m=map(int,input().split())
 y=n*m
 for x in range(n*m):
  a=1
  b=1
  d={(1,1):1}
  count=1
  if x==0:
   print(n*m,end=" ")
   continue
  while(True):
   b=b+x+1
   if(b>m):
    u=b-m
    if(u%m==0):
     a=a+u//m
     b=m
    else:
     a=a+(u//m)+1
     b=u%m
   if a>n:
    break
   else:
    d[(a,b)]=1
    count+=1
  a=1
  b=1
  while(True):
   a=a+x+1
   if(a>n):
    u=a-n
    if(u%n==0):
     b=b+u//n
     a=n
    else:
     b=b+(u//n)+1
     a=u%n
   if b>m:
    break
   else:
    if (a,b) not in d.keys():
     count+=1
  print(count,end=" ")
 print("")
  
   


for _ in range(int(input())):
 n,m=map(int,input().split())
 lim=n*m+1
 k=lim-1
 lst=[int(num) for num in range(1,lim)]
 lst2=[]
 for val in range(1,m+1):
  for val2 in range(n):
   lst2.append(val+(m*(val2)))
 for val_k in range(k):
  lst_k=[]
  for index in range(0,lim-1,val_k+1):
   lst_k.append(lst[index])
   lst_k.append(lst2[index])
  print(len(set(lst_k)),end=" ")
 print()

for x in range(int(input())):
 n,m=map(int,input().split())
 y=n*m
 l=[(1,1)]
 for x in range(n*m):
  l=[(1,1)]
  a=1
  b=1
  if x==0:
   print(n*m,end=" ")
   continue
  while(True):
   b=b+x+1
   if(b>m):
    u=b-m
    if(u%m==0):
     a=a+u//m
     b=m
    else:
     a=a+(u//m)+1
     b=u%m
   if a>n:
    break
   else:
    l.append((a,b))
  a=1
  b=1
  while(True):
   a=a+x+1
   if(a>n):
    u=a-n
    if(u%n==0):
     b=b+u//n
     a=n
    else:
     b=b+(u//n)+1
     a=u%n
   if b>m:
    break
   else:
    l.append((a,b))
  print(len(set(l)),end=" ")
 print("")
  
   


for x in range(int(input())):
 n,m=map(int,input().split())
 y=n*m
 l=[(1,1)]
 for x in range(n*m):
  l=[(1,1)]
  a=1
  b=1
  while(True):
   b=b+x+1
   if(b>m):
    u=b-m
    if(u%m==0):
     a=a+u//m
     b=m
    else:
     a=a+(u//m)+1
     b=u%m
   if a>n:
    break
   else:
    l.append((a,b))
  a=1
  b=1
  while(True):
   a=a+x+1
   if(a>n):
    u=a-n
    if(u%n==0):
     b=b+u//n
     a=n
    else:
     b=b+(u//n)+1
     a=u%n
   if b>m:
    break
   else:
    l.append((a,b))
  print(len(set(l)),end=" ")
 print("")
  
   


# cook your dish here
t=int(input())
l =[]
for i in range(0,t):
 ele=list(map(int,input().split()))
 l.append(ele)
for i in range(0, t):
 n=l[i][0]
 m=l[i][1]
 f1=[]
 f2=[]
 for j in range(1,n+1):
  for h in range(1, m + 1):
   f1.append((j,h))
 for j in range(1,m+1):
  for h in range(1, n+ 1):
   f2.append((h,j))

 for k in range(0,n*m):
  if k==0:
   print(n*m,end=' ')
  else:
   y=[]
   z=[]
   e=0
   while e*(k+1)<n*m:

    y.append(f1[e*(k+1)])
    z.append(f2[e*(k+1)])
    e=e+1

   for x in z:
    if x not in y:
     y.append(x)

   print(len(y),end=' ')

# cook your dish here
ans = set()
for _ in range(int(input())):
 r,c = map(int,input().split())
 count = 0
 for i in range(0,r*c):        
  ans.clear()
  for x in range(0,r*c,i+1):
   a = x//r
   b = x%r
   ans.add((a,b))
   a = x%c
   b = x//c
   ans.add((a,b))
  
  print(len(ans), end= " ")

ans = [[False for _ in range(1000)] for _ in range(1000)]
for _ in range(int(input())):
 r,c = map(int,input().split())
 count = 0
 for i in range(0,r*c):
  val = 0
  for x in range(0,r*c,i+1):
   a = x//r
   b = x%r
   
   # ans.add((a,b))
   if not ans[a][b]:
    ans[a][b] = True
    val+=1
   a = x%c
   b = x//c
   # ans.add((a,b))
   if not ans[a][b]:
    ans[a][b]=True
    val+=1
   
  for x in range(0,r*c,i+1):
   a = x//r
   b = x%r 
   ans[a][b]=False
   a = x%c
   b = x//c
   ans[a][b]=False
   
  
  print(val, end= " ")

ans = [[False for _ in range(1001)] for _ in range(1001)]
for _ in range(int(input())):
 r,c = map(int,input().split())
 count = 0
 for i in range(0,r*c):
  val = 0
  for x in range(0,r*c,i+1):
   a = x//r
   b = x%r
   
   # ans.add((a,b))
   ans[a][b] = True
   a = x%c
   b = x//c
   # ans.add((a,b))
   ans[a][b]=True
   
  for x in range(0,r*c,i+1):
   
   a = x//r
   b = x%r
   
   if ans[a][b] == True:
    ans[a][b]=False
    val+=1
   a = x%c
   b = x//c
   if ans[a][b] == True:
    ans[a][b]=False
    val+=1
   
  
  print(val, end= " ")

# cook your dish here
for _ in range(int(input())):
 r,c = map(int,input().split())
 count = 0
 for i in range(0,r*c):        
  ans = set()
  for x in range(0,r*c,i+1):
   a = x//r
   b = x%r
   ans.add((a,b))
   a = x%c
   b = x//c
   ans.add((a,b))
  
  print(len(ans), end= " ")

# cook your dish here
for _ in range(int(input())):
 r,c = map(int,input().split())
 count = 0
 for i in range(0,r*c):        
  ans = list()
  for x in range(0,r*c,i+1):
   a = x//r
   b = x%r
   ans.append((a,b))
   a = x%c
   b = x//c
   ans.append((a,b))
  
  print(len(set(ans)), end= " ")