There is a grid with $n$ rows and $m$ columns, and three types of cells:

An empty cell, denoted with '.'.

A stone, denoted with '*'.

An obstacle, denoted with the lowercase Latin letter 'o'.

All stones fall down until they meet the floor (the bottom row), an obstacle, or other stone which is already immovable. (In other words, all the stones just fall down as long as they can fall.)

Simulate the process. What does the resulting grid look like?


-----Input-----

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

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 50$) — the number of rows and the number of columns in the grid, respectively.

Then $n$ lines follow, each containing $m$ characters. Each of these characters is either '.', '*', or 'o' — an empty cell, a stone, or an obstacle, respectively.


-----Output-----

For each test case, output a grid with $n$ rows and $m$ columns, showing the result of the process.

You don't need to output a new line after each test, it is in the samples just for clarity.


-----Examples-----

Input
3
6 10
.*.*....*.
.*.......*
...o....o.
.*.*....*.
..........
.o......o*
2 9
...***ooo
.*o.*o.*o
5 5
*****
*....
*****
....*
*****
Output
..........
...*....*.
.*.o....o.
.*........
.*......**
.o.*....o*

....**ooo
.*o**o.*o

.....
*...*
*****
*****
*****


-----Note-----

None

Difficulty: EASY
Tags: Graph traversal

Implementation

Starter code:

Solutions:
for _ in range(int(input())):
	(n, _) = map(int, input().split())
	a = map(''.join, zip(*(input() for _ in range(n))))
	a = ('o'.join((''.join(sorted(y, reverse=True)) for y in x.split('o'))) for x in a)
	for x in zip(*a):
		print(''.join(x))


def change(grid, n, m):
	for i in range(m):
		b = n - 1
		s = n
		while b >= 0:
			if grid[b][i] == '*':
				grid[b][i] = '.'
				grid[s - 1][i] = '*'
				s -= 1
			elif grid[b][i] == 'o':
				s = b
			b -= 1
t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split(' ')]
	grid = []
	for i in range(n):
		grid.append(list(input()))
	change(grid, n, m)
	for i in range(n):
		print(''.join(grid[i]))


import collections

def func(n, m, arr):
	k = 0
	for j in range(m):
		k = n - 1
		for i in range(n - 1, -1, -1):
			if arr[i][j] == 'o':
				k = i - 1
			elif arr[i][j] == '*':
				arr[i][j] = '.'
				arr[k][j] = '*'
				k -= 1
	arr1 = []
	for i in arr:
		arr1.append(''.join(i))
	return arr1
t = int(input())
for i in range(t):
	arr = list(map(int, input().rstrip().split()))
	n = arr[0]
	m = arr[1]
	arr = []
	for i in range(n):
		s = input()
		s = list(s)
		arr.append(s)
	ans = func(n, m, arr)
	for i in range(n):
		print(ans[i])


from collections import Counter, deque, defaultdict
from math import *
from bisect import bisect_right
mod = 1000000007

def solve():
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(input()))
	for i in range(m):
		j = n - 1
		cur = -1
		while j >= 0:
			if l[j][i] == '.':
				cur = j
				break
			j -= 1
		if cur == '-1':
			continue
		for j in range(cur - 1, -1, -1):
			if l[j][i] == '*':
				(l[cur][i], l[j][i]) = (l[j][i], l[cur][i])
				cur -= 1
			elif l[j][i] == 'o':
				cur = j - 1
	for i in l:
		print(''.join(i))
t = int(input())
for num in range(t):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		a = list(input())
		l.append(a)
	for i in range(m):
		avail = -1
		for j in range(n - 1, -1, -1):
			if l[j][i] == '*':
				if avail == -1:
					pass
				else:
					l[avail][i] = '*'
					l[j][i] = '.'
					avail -= 1
			elif l[j][i] == '.':
				if avail == -1:
					avail = j
			elif l[j][i] == 'o':
				avail = -1
	for i in l:
		print(''.join(i))


x = int(input())

def trans(m, n, grid):
	for i in range(n):
		b = m - 1
		s = m
		while b >= 0:
			if grid[b][i] == '*':
				grid[b][i] = '.'
				grid[s - 1][i] = '*'
				s -= 1
			elif grid[b][i] == 'o':
				s = b
			b -= 1
for jj in range(x):
	(m, n) = [int(i) for i in input().split(' ')]
	grid = []
	for i in range(m):
		grid.append(list(input()))
	trans(m, n, grid)
	for i in range(m):
		print(''.join(grid[i]))


import math

def solve():
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		mat.append(list(input()))
	ct = 0
	for j in range(m):
		for i in range(n):
			if mat[i][j] == 'o':
				for x in range(ct):
					mat[i - 1][j] = '*'
					i = i - 1
				ct = 0
			elif i == n - 1:
				if mat[i][j] == '*':
					ct += 1
				for x in range(ct):
					mat[i][j] = '*'
					i -= 1
				ct = 0
			elif mat[i][j] == '*':
				mat[i][j] = '.'
				ct += 1
	for i in range(n):
		print(''.join(mat[i]))
t = int(input())
for i in range(t):
	solve()


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		s = list(input())[:m]
		grid.append(s)
	for c in range(m):
		place = n - 1
		for r in range(n - 1, -1, -1):
			if grid[r][c] == '.':
				continue
			if grid[r][c] == 'o':
				place = r - 1
			else:
				grid[r][c] = '.'
				grid[place][c] = '*'
				place -= 1
	for i in grid:
		print(''.join(i))
t = int(input())
while t != 0:
	solve()
	t -= 1


import sys
getline = sys.stdin.readline

def read_int():
	return int(getline())

def read_ints():
	return list(map(int, getline().split()))

def read_s():
	return str(getline().strip())

def read_ss():
	return list(map(str, getline().strip().split()))
t = read_int()
for _ in range(t):
	(n, m) = read_ints()
	arr = []
	for i in range(n):
		row = read_s()
		arr.append(row)
	ans = [['.'] * m for i in range(n)]
	for x in range(m):
		last = n - 1
		for y in reversed(range(n)):
			c = arr[y][x]
			if c == 'o':
				ans[y][x] = 'o'
				last = y - 1
			if c == '*':
				ans[last][x] = '*'
				last -= 1
	for line in ans:
		print(''.join(line))


def solve():
	(n, m) = map(int, input().split())
	g = [[c for c in input().strip()] for _ in range(n)]
	for j in range(m):
		last = n - 1
		for i in range(n - 1, -1, -1):
			if g[i][j] == 'o':
				last = i - 1
			elif g[i][j] == '*':
				(g[i][j], g[last][j]) = (g[last][j], g[i][j])
				last -= 1
	for i in range(n):
		print(''.join(g[i]))
tt = int(input())
for i in range(1, tt + 1):
	solve()


T = int(input())
for _ in range(T):
	(m, n) = list(map(int, input().split()))
	arr = []
	for _ in range(m):
		arr.append(input())
	ans = [['.' for _ in range(n)] for _ in range(m)]
	for j in range(n):
		cur_level = m - 1
		for i in range(m - 1, -1, -1):
			if arr[i][j] == 'o':
				ans[i][j] = 'o'
				cur_level = i - 1
			elif arr[i][j] == '*':
				ans[cur_level][j] = '*'
				cur_level -= 1
	for i in range(m):
		print(''.join(ans[i]))


I = input
for _ in range(int(I())):
	(n, m) = map(int, I().split())
	grid = [I().strip() for __ in range(n)]
	res = []
	for col in range(m):
		newcol = ''
		for seg in ''.join((grid[row][col] for row in range(n))).split('o'):
			newcol += '.' * seg.count('.') + '*' * seg.count('*') + 'o'
		res.append(newcol[0:-1])
	for row in range(n):
		print(''.join((res[col][row] for col in range(m))))


t = int(input())
for _ in range(t):
	(n, m) = [int(s) for s in input().split(' ')]
	ans = [['.' for i in range(m)] for j in range(n)]
	grid = []
	for i in range(n):
		row = input().strip()
		grid.append(row)
	for j in range(m):
		stoneCnt = 0
		for i in range(n):
			if grid[i][j] == '*':
				stoneCnt += 1
			elif grid[i][j] == 'o':
				ans[i][j] = 'o'
				curRow = i - 1
				while stoneCnt:
					ans[curRow][j] = '*'
					curRow -= 1
					stoneCnt -= 1
		if stoneCnt:
			curRow = n - 1
			while stoneCnt:
				ans[curRow][j] = '*'
				curRow -= 1
				stoneCnt -= 1
	for i in range(n):
		print(''.join(ans[i]))


n = int(input())
for _ in range(n):
	(x, y) = map(int, input().split())
	arr = []
	for __ in range(x):
		arr.append(list(input()))
	for zy in range(0, y, +1):
		free_slots = 0
		for zx in range(x - 1, -1, -1):
			if arr[zx][zy] == '*':
				if free_slots:
					arr[zx + free_slots][zy] = '*'
					arr[zx][zy] = '.'
			elif arr[zx][zy] == 'o':
				free_slots = 0
			else:
				free_slots += 1
	for line in arr:
		print(''.join(line))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	L = []
	for i in range(n):
		L.append(input())
	res = [['.' for j in range(m)] for i in range(n)]
	for j in range(m):
		cur = n - 1
		for i in reversed(range(n)):
			if L[i][j] == '*':
				res[i][j] = '.'
				res[cur][j] = '*'
				cur -= 1
			elif L[i][j] == 'o':
				res[i][j] = 'o'
				cur = i - 1
	for i in range(n):
		print(''.join(res[i]))


for _ in range(int(input())):
	(h, w) = [int(x) for x in input().split()]
	lines = [input() for x in range(h)]
	columns = ['' for col in range(w)]
	for x in range(w):
		columns[x] = ''.join((lines[y][x] for y in range(h)))
	for i_column in range(len(columns)):
		new_column = ''
		cache = [0, 0]
		for letter in columns[i_column]:
			if letter == 'o':
				new_column += '.' * cache[0] + '*' * cache[1] + 'o'
				cache = [0, 0]
			else:
				cache[letter == '*'] += 1
		new_column += '.' * cache[0] + '*' * cache[1]
		columns[i_column] = new_column
	new_lines = ['' for lin in range(h)]
	for y in range(h):
		new_lines[y] = ''.join((columns[x][y] for x in range(w)))
	print(*new_lines, sep='\n')


for _ in range(int(input())):
	[n, m] = list(map(int, input().split()))
	mat = []
	for __ in range(n):
		mat.append([i for i in input()])
	new = [['.' for i in range(m)] for j in range(n)]
	for j in range(m):
		c = 0
		for i in range(n):
			if mat[i][j] == '*':
				c += 1
			elif mat[i][j] == 'o':
				new[i][j] = 'o'
				for k in range(1, c + 1):
					new[i - k][j] = '*'
				c = 0
		if c:
			for k in range(c):
				new[n - 1 - k][j] = '*'
			c = 0
	for i in new:
		print(''.join(i))


for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	mat = []
	for i in range(n):
		mat.append(list(input()))
	for j in range(m):
		lev = n
		for i in range(n - 1, -1, -1):
			if mat[i][j] == 'o':
				lev = i
			elif mat[i][j] == '*':
				mat[i][j] = '.'
				mat[lev - 1][j] = '*'
				lev -= 1
	for i in mat:
		print(''.join(i))


from collections import Counter, defaultdict
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ar = []
	for _ in range(n):
		ar.append(input())
	res = []
	for col in range(m):
		stack = []
		prev = 0
		for row in reversed(range(n)):
			if ar[row][col] == '*':
				if prev < len(stack):
					stack[prev] = '*'
					stack.append('.')
				else:
					stack.append('*')
				prev += 1
			elif ar[row][col] == 'o':
				stack.append('o')
				prev = len(stack)
			else:
				stack.append('.')
		res.append(stack[::-1])
	res2 = []
	for row in range(n):
		res2.append(''.join((res[col][row] for col in range(m))))
	for x in res2:
		print(x)


def task(n, m, a):
	for j in range(0, m):
		stones = 0
		spaces = 0
		for i in range(0, n):
			c = a[i][j]
			if c == '.' and i < n - 1:
				spaces += 1
			elif c == '*' and i < n - 1:
				stones += 1
			elif c == 'o':
				for k in range(1, spaces + stones + 1):
					if stones > 0:
						a[i - k][j] = '*'
						stones -= 1
					else:
						a[i - k][j] = '.'
				spaces = 0
				stones = 0
			elif (c == '.' or c == '*') and i == n - 1:
				if c == '.':
					spaces += 1
				if c == '*':
					stones += 1
				for k in range(0, spaces + stones):
					if stones > 0:
						a[i - k][j] = '*'
						stones -= 1
					else:
						a[i - k][j] = '.'
				spaces = 0
				stones = 0
	for i in range(0, n):
		str = ''
		for j in range(0, m):
			str += a[i][j]
		print(str)
t = int(input())
for i in range(0, t):
	(n, m) = list(map(int, input().split()))
	a = []
	for j in range(0, n):
		a.append(list(input()))
	task(n, m, a)


def supersplit(k):
	p = []
	for i in k:
		p.append(i)
	return p

def antisplit(p):
	k = ''
	for i in p:
		k += i
	return k
for t in range(int(input())):
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		grid.append(supersplit(input()))
	for i in range(m - 1, -1, -1):
		g = n - 1
		for j in range(n - 1, -1, -1):
			if grid[j][i] == 'o':
				g = j - 1
			elif grid[j][i] == '*':
				grid[j][i] = '.'
				grid[g][i] = '*'
				g -= 1
	for i in grid:
		print(antisplit(i))


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	a = [list(input()) for _ in range(n)] + [['o'] * m]
	for j in range(m):
		beg = cnt = 0
		for i in range(n + 1):
			if a[i][j] == '*':
				cnt += 1
			elif a[i][j] == 'o':
				for k in range(beg, i - cnt):
					a[k][j] = '.'
				for k in range(i - cnt, i):
					a[k][j] = '*'
				beg = i + 1
				cnt = 0
	for i in range(n):
		print(''.join(a[i]))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	grid = []
	for _ in range(n):
		row = list(input())
		grid.append(row)
	for col in range(m):
		last = n - 1
		for row in range(n - 1, -1, -1):
			if grid[row][col] == '.':
				last = max(last, row)
			elif grid[row][col] == '*':
				grid[row][col] = '.'
				grid[last][col] = '*'
				last -= 1
			else:
				last = row - 1
	for row in grid:
		print(''.join(row))


cases = int(input(''))
tests = []
for i in range(0, cases):
	(n, m) = input('').split(' ')
	n = int(n)
	m = int(m)
	arr = []
	for j in range(0, n):
		arr.append(list(input('')))
	tests.append((n, m, arr))
for (n, m, arr) in tests:
	for col in range(0, m):
		next_obs = n - 1
		for row in range(0, n):
			row = n - 1 - row
			if arr[row][col] == 'o':
				next_obs = row - 1
			elif arr[row][col] == '*':
				arr[row][col] = '.'
				arr[next_obs][col] = '*'
				next_obs -= 1
			else:
				pass
	for a_row in range(0, n):
		arr[a_row] = ''.join(arr[a_row])
	print('\n'.join(arr))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	matrix = [list(input()) for x in range(n)]
	for j in range(m):
		free = -1
		for i in range(n - 1, -1, -1):
			if matrix[i][j] == '.' and free == -1:
				free = i
			if matrix[i][j] == '*':
				if free > -1:
					matrix[free][j] = '*'
					matrix[i][j] = '.'
					free -= 1
			if matrix[i][j] == 'o':
				free = -1
	for i in matrix:
		print(''.join(i))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	t = [[] for i in range(n)]
	for i in range(n):
		t[i] = list(input())
	for j in range(m):
		lst = n - 1
		for i in range(n - 1, -1, -1):
			if t[i][j] == 'o':
				lst = i - 1
			elif t[i][j] == '*':
				t[i][j] = '.'
				t[lst][j] = '*'
				lst -= 1
	for i in range(n):
		print(''.join(t[i]))


for inh in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())
	ans = [''] * n
	for i in range(m):
		last = n - 1
		curr = n - 1
		while curr >= 0:
			if a[curr][i] == 'o':
				while last > curr:
					ans[last] += '.'
					last -= 1
				ans[last] += 'o'
				last -= 1
				curr -= 1
			elif a[curr][i] == '.':
				curr -= 1
			else:
				ans[last] += '*'
				curr -= 1
				last -= 1
		while last >= 0:
			ans[last] += '.'
			last -= 1
	for i in range(n):
		print(ans[i])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = []
	for i in range(n):
		g.append(list(input()))
	for c in range(m):
		stones = 0
		for r in range(n):
			if r != n - 1 and g[r][c] == '*':
				stones += 1
				g[r][c] = '.'
			elif g[r][c] == 'o' or (r == n - 1 and g[r][c] == '*'):
				for up in range(stones):
					g[r - up - 1][c] = '*'
				stones = 0
			if r == n - 1 and g[r][c] == '.':
				for up in range(stones):
					g[r - up][c] = '*'
				stones = 0
	for i in range(n):
		print(''.join(g[i]))


t = int(input())
for _ in range(t):
	(r, c) = tuple([int(x) for x in input().split(' ')])
	grid = []
	for _ in range(r):
		grid.append(list(input()))
	for column in range(c):
		j = r - 1
		segment_length = 0
		while j >= 0:
			if grid[j][column] == '*':
				(grid[j][column], grid[j + segment_length][column]) = (grid[j + segment_length][column], grid[j][column])
			elif grid[j][column] == '.':
				segment_length += 1
			else:
				segment_length = 0
			j -= 1
	for row in range(r):
		print(''.join(grid[row]))


import sys
input = sys.stdin.readline
for _ in [0] * int(input()):
	(n, m) = map(int, input().split())
	s = [''] * m
	for _ in [0] * n:
		s = [s[i] + j for (i, j) in zip(range(m), input())]
	col = [''] * n
	k = 0
	for i in s:
		bl = 0
		x = ''
		for j in i[::-1]:
			if j == 'o':
				x = j + '.' * bl + x
				bl = 0
			elif j == '*':
				x = j + x
			else:
				bl = bl + 1
		x = '.' * bl + x
		col = [col[ind] + val for (val, ind) in zip(x, range(n))]
		k = k + 1
	for j in col:
		print(j)


t = int(input())
for _ in range(t):
	cs = input().split()
	n = int(cs[0])
	m = int(cs[1])
	grid = [[None for _ in range(m)] for _ in range(n)]
	for i in range(n):
		line = input()
		for j in range(m):
			grid[i][j] = line[j]
	result = [['.' for _ in range(m)] for _ in range(n)]
	for j in range(m):
		stones = 0
		for i in range(n):
			if grid[i][j] == '*':
				stones += 1
			elif grid[i][j] == 'o':
				result[i][j] = 'o'
				for k in range(1, stones + 1):
					result[i - k][j] = '*'
				stones = 0
		for k in range(1, stones + 1):
			result[n - k][j] = '*'
	for i in range(n):
		print(''.join(result[i]))


def fall(col):
	marker = n
	for i in range(n - 1, -1, -1):
		if col[i] == 'o':
			marker = i
		elif col[i] == '*':
			if i != marker - 1:
				col[i] = '.'
				col[marker - 1] = '*'
				marker -= 1
			else:
				marker -= 1
				continue
	return col
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	transpose = []
	for i in range(m):
		transpose.append([])
	for i in range(n):
		x = input()
		for j in range(m):
			transpose[j].append(x[j])
	for i in range(m):
		fall(transpose[i])
	for i in range(n):
		ans = ''
		for j in range(m):
			ans += transpose[j][i]
		print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = [[] for _ in range(n)]
	for i in range(n):
		arr[i] = list(input())
	for j in range(0, m):
		last = n - 1
		for i in range(n - 1, -1, -1):
			if arr[i][j] == 'o':
				last = i - 1
			elif arr[i][j] == '*':
				(arr[i][j], arr[last][j]) = (arr[last][j], arr[i][j])
				last -= 1
	for a in arr:
		print(''.join(a))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	li = []
	for i in range(n):
		s = input()
		li.append([char for char in s])
	for i in range(m):
		st = 0
		obs = 0
		for j in range(n):
			if li[j][i] == '*':
				st += 1
				li[j][i] = '.'
			elif li[j][i] == 'o':
				for k in range(j - 1, j - 1 - st, -1):
					li[k][i] = '*'
				st = 0
			if j == n - 1 and st != 0 and (li[j][i] != 'o'):
				for k in range(j, j - st, -1):
					li[k][i] = '*'
				st = 0
	for i in range(n):
		s = ''
		for j in range(m):
			s += li[i][j]
		print(s)


c = input()
for _ in range(int(c)):
	b = input().split()
	a = []
	for i in range(int(b[0])):
		a.append(list(input()))
	for i in range(int(b[1])):
		count = 0
		row = int(b[0]) - 1
		for j in range(int(b[0])):
			if a[row][i] == '.':
				count += 1
			elif a[row][i] == 'o':
				count = 0
			else:
				(a[row][i], a[row + count][i]) = ('.', a[row][i])
			row -= 1
	for i in range(int(b[0])):
		print(''.join(a[i]))


nT = int(input())
while nT > 0:
	mn = input()
	mn = mn.split(' ')
	(m, n) = (int(mn[0]), int(mn[1]))
	board = []
	for i in range(m):
		strLine = [*input()]
		board.append(strLine)
	for j in range(n):
		cnt = 0
		for i in range(m):
			if board[i][j] == '.':
				continue
			if board[i][j] == '*':
				board[i][j] = '.'
				cnt += 1
			if board[i][j] == 'o' and cnt > 0:
				for i1 in range(i - 1, i - (1 + cnt), -1):
					board[i1][j] = '*'
				cnt = 0
		if cnt > 0:
			for i1 in range(m - 1, m - 1 - cnt, -1):
				board[i1][j] = '*'
	for l in board:
		print(''.join(l))
	nT -= 1


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	l = []
	(n, m) = map(int, input().split())
	for i in range(n):
		l1 = list(input())
		l.append(l1)
	x = 0
	y = 0
	v = 0
	for j in range(m):
		for i in range(n):
			if l[i][j] == '*':
				x = x + 1
			elif l[i][j] == '.':
				y = y + 1
			elif l[i][j] == 'o':
				for k in range(v, v + y):
					l[k][j] = '.'
				for k in range(v + y, v + y + x):
					l[k][j] = '*'
				v = i + 1
				y = 0
				x = 0
		for k in range(v, v + y):
			l[k][j] = '.'
		for k in range(v + y, v + y + x):
			l[k][j] = '*'
		v = 0
		y = 0
		x = 0
	for i in range(n):
		s = ''
		for j in range(m):
			s = s + l[i][j]
		print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [input() for _ in range(n)]
	b = [''] * m
	b1 = b.copy()
	a1 = [''] * n
	for i in range(n):
		for j in range(m):
			b[j] += a[i][j]
	for row in range(m):
		kam = 0
		s = ''
		for i in b[row]:
			if i == '*':
				kam += 1
			elif i == '.':
				s += '.'
			else:
				s += '*' * kam + 'o'
				kam = 0
		else:
			s += '*' * kam
		b1[row] = s
	for i in range(n):
		for j in range(m):
			a1[i] += b1[j][i]
	for i in a1:
		print(i)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		a = input()
		arr.append(a)
	ans = [['.' for i in range(m)] for i in range(n)]
	for i in range(n):
		for j in range(m):
			if arr[i][j] == 'o':
				ans[i][j] = 'o'
	for i in range(m):
		c = 0
		base = n
		for j in range(n - 1, -1, -1):
			if arr[j][i] == 'o':
				for x in range(base - 1, base - 1 - c, -1):
					ans[x][i] = '*'
				base = j
				c = 0
			elif arr[j][i] == '*':
				c += 1
		for x in range(base - 1, base - 1 - c, -1):
			ans[x][i] = '*'
	for i in range(n):
		s = ''
		for j in range(m):
			s = s + ans[i][j]
		print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[c for c in input()] for r in range(n)]
	for c in range(m):
		k = 0
		for r in range(n):
			if a[r][c] == '*':
				k += 1
				a[r][c] = '.'
			if r >= n - 1 or a[r + 1][c] == 'o':
				for z in range(k):
					a[r - z][c] = '*'
				k = 0
	for r in range(n):
		s = ''
		for c in range(m):
			s += a[r][c]
		print(s)


def func(arr):
	return ''.join(arr)
for t in range(int(input())):
	(r, c) = map(int, input().split())
	grid = []
	for i in range(r):
		x = list(input())
		grid.append(x)
	for j in range(c):
		extract = []
		for k in range(r):
			extract.append(grid[k][j])
		stones = []
		empty = []
		obstacles = []
		temp_e = 0
		temp_s = 0
		for l in range(r):
			if extract[l] == '.':
				temp_e += 1
			if extract[l] == '*':
				temp_s += 1
			if extract[l] == 'o':
				obstacles.append(l)
				stones.append(temp_s)
				temp_s = 0
				empty.append(temp_e)
				temp_e = 0
		if temp_s != 0:
			stones.append(temp_s)
		if temp_e != 0:
			empty.append(temp_e)
		result = ''
		while True:
			if len(stones) > len(obstacles):
				result += '*' * stones[-1]
				stones.pop()
			if len(empty) > len(obstacles):
				result += '.' * empty[-1]
				empty.pop()
			if len(obstacles) != 0:
				result += 'o'
				obstacles.pop()
			if len(empty) == 0 and len(stones) == 0 and (len(obstacles) == 0):
				break
		result = list(result[::-1])
		for m in range(r):
			grid[m][j] = result[m]
	grid = list(map(func, grid))
	print('\n'.join(grid))


for _ in range(int(input())):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	lis = []
	for i in range(n):
		s = input()
		lis1 = []
		for p in s:
			lis1.append(p)
		lis.append(lis1)
	for i in range(m):
		for j in range(n - 1, -1, -1):
			if lis[j][i] == '.' and j == n - 1:
				t = n
			elif lis[j][i] == '.':
				continue
			elif j == n - 1:
				t = j
			elif lis[j][i] == '*':
				temp = lis[t - 1][i]
				lis[t - 1][i] = lis[j][i]
				lis[j][i] = temp
				t = t - 1
			else:
				t = j
	for i in lis:
		print(''.join(i))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	g = []
	(o, s) = ([], [[] for j in range(m)])
	for i in range(n):
		r = input()
		g.append(list(r))
		for (j, c) in enumerate(r):
			if c == 'o':
				o.append((j, -i))
			if c == '*':
				s[j].append(-i)
	o.extend(((i, 1) for i in range(m)))
	o.extend(((i, -n) for i in range(m)))
	o.sort()
	os = []
	for ((j1, i1), (j2, i2)) in zip(o, o[1:]):
		if j1 != j2:
			continue
		os.append((j1, i1, sum((1 for i in s[j1] if i1 < i < i2))))
	out = [['.'] * m for _ in range(n)]
	for (j, i, c) in os:
		i = -i
		if 0 <= i < n:
			out[i][j] = 'o'
		for k in range(1, c + 1):
			out[i - k][j] = '*'
	for l in out:
		print(''.join(l))


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		x = input().strip()
		tmp = []
		for j in x:
			tmp.append(j)
		l.append(tmp[:])
	l.append(['o'] * m)
	for i in range(m):
		x = 0
		for j in range(n + 1):
			if l[j][i] == 'o':
				k = j - 1
				while k > -1 and l[k][i] != 'o':
					if x == 0:
						l[k][i] = '.'
					else:
						l[k][i] = '*'
						x -= 1
					k -= 1
			elif l[j][i] == '*':
				x += 1
	for i in range(n):
		x = ''
		for j in range(m):
			x += l[i][j]
		print(x)


import math
import functools
from collections import *

def Solve():
	(r, c) = [int(i) for i in input().split()]
	ar = []
	for _ in range(r):
		temp = input()
		ar.append(temp)
	d = {}
	for j in range(c):
		cnt = 0
		for i in range(r):
			if ar[i][j] == '*':
				ar[i] = ar[i][:j] + '.' + ar[i][j + 1:]
				cnt += 1
			elif ar[i][j] == 'o' and cnt:
				d[i, j] = cnt
				cnt = 0
		if cnt:
			d[i + 1, j] = cnt
	for ((x, y), cnt) in d.items():
		while cnt > 0:
			ar[x - 1] = ar[x - 1][:y] + '*' + ar[x - 1][y + 1:]
			x -= 1
			cnt -= 1
	print('\n'.join(ar))

def main():
	x = int(input(''))
	for _ in range(x):
		Solve()
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lista = []
	for i in range(0, n):
		lista.append(input())
	updated_column = []
	for i in range(0, m):
		l = ''
		a = 0
		b = 0
		for j in range(0, n):
			if lista[j][i] == '*':
				a += 1
			if lista[j][i] == '.':
				b += 1
			if lista[j][i] == 'o':
				for k in range(b):
					l += '.'
				for k in range(a):
					l += '*'
				l += 'o'
				a = 0
				b = 0
			if j == n - 1 and lista[j][i] != 'o':
				for k in range(b):
					l += '.'
				for k in range(a):
					l += '*'
		updated_column.append(l)
	for j in range(n):
		p = ''
		for i in range(m):
			p += updated_column[i][j]
		print(p)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	mat = [[c for c in input()] for _ in range(m)]
	Y = [m - 1 for _ in range(n)]
	for i in range(m - 1, -1, -1):
		for j in range(n):
			if mat[i][j] == '*':
				mat[i][j] = '.'
				mat[Y[j]][j] = '*'
				Y[j] -= 1
			elif mat[i][j] == 'o':
				Y[j] = i - 1
	for row in mat:
		print(*row, sep='')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = [list(input()) for _ in range(n)]
	for k in range(m):
		last = n - 1
		for i in range(n - 1, -1, -1):
			if s[i][k] == '*':
				(s[i][k], s[last][k]) = (s[last][k], s[i][k])
				last -= 1
			elif s[i][k] == 'o':
				last = i - 1
	for k in s:
		print(*k, sep='')


def help():
	(n, m) = list(map(int, input().split()))
	g = []
	for i in range(n):
		l = list(input())
		g.append(l)
	for i in range(m):
		c = 0
		for j in range(n):
			if g[j][i] == '*':
				c += 1
				g[j][i] = '.'
			if g[j][i] == 'o':
				t = j - 1
				while c > 0:
					g[t][i] = '*'
					c -= 1
					t -= 1
				c = 0
			t = n - 1
		while c > 0:
			g[t][i] = '*'
			c -= 1
			t -= 1
	for i in range(n):
		for j in range(m):
			print(g[i][j], end='')
		print()
for _ in range(int(input())):
	help()


import collections

def print_matrix(g, n, m):
	for i in range(n):
		for j in range(m):
			print(g[i][j], end='')
		print()

def solve(n, m, g):
	matrix = [['.' for x in range(m)] for y in range(n)]
	for x in range(n):
		for y in range(m):
			if g[x][y] == 'o':
				matrix[x][y] = 'o'
	j = 0
	i = 0
	while j < m:
		nStone = 0
		while i < n and g[i][j] != 'o':
			if g[i][j] == '*':
				nStone += 1
			i += 1
		t = i - 1
		while nStone:
			matrix[t][j] = '*'
			t -= 1
			nStone -= 1
		if i != n:
			i += 1
			continue
		i = 0
		j += 1
	print_matrix(matrix, n, m)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = []
	for i in range(n):
		g.append([ch for ch in input()])
	solve(n, m, g)


def inp(*, cf=lambda x: x):
	return cf(input())

def inpint():
	return inp(cf=int)

def inp_line(*, cf=lambda x: x, s=' '):
	return list(map(cf, input().split(s)))

def inpints():
	return inp_line(cf=int)

def stones_until_obstacle(grid, i, j):
	stones = 0
	while i >= 0 and grid[i][j] != 'o':
		if grid[i][j] == '*':
			stones += 1
		i -= 1
	return (i, stones)

def test_case(case):
	(n, m) = inpints()
	grid = []
	for i in range(n):
		grid.append(list(inp()))
	if n == 1:
		for j in range(m):
			print(grid[0][j], end='')
		print()
		return
	result = [['.' for _ in range(m)] for _ in range(n)]
	for i in range(n):
		for j in range(m):
			if grid[i][j] == 'o':
				result[i][j] = 'o'
	for j in range(m):
		i = n - 1
		if grid[i][j] == 'o':
			i -= 1
		while i >= 0:
			(next_obstacle, stones) = stones_until_obstacle(grid, i, j)
			for s in range(i - stones + 1, i + 1):
				result[s][j] = '*'
			i = next_obstacle
			if i >= 0:
				i -= 1
	for i in range(n):
		for j in range(m):
			print(result[i][j], end='')
		print()

def main():
	T = inpint()
	for t in range(1, T + 1):
		test_case(t)
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [list(input()) for i in range(n)]
	a.append(['o'] * m)
	ans = [['.'] * m for i in range(n + 1)]
	for i in range(n + 1):
		for j in range(m):
			if a[i][j] == 'o':
				ans[i][j] = 'o'
				kk = 0
				for k in reversed(range(i)):
					if a[k][j] == 'o':
						break
					elif a[k][j] == '*':
						kk += 1
				for k in range(i - kk, i):
					ans[k][j] = '*'
	for i in range(n):
		print(*ans[i], sep='')


def resi():
	(n, m) = map(int, input().split())
	res = [[''] * m for i in range(n + 1)]
	matrica = [['.'] * m for i in range(n + 1)]
	for i in range(n):
		s = input()
		for j in range(m):
			matrica[i][j] = s[j]
	for j in range(m):
		matrica[n][j] = 'o'
	for j in range(m):
		br = 0
		for i in range(n + 1):
			if matrica[i][j] == '*':
				br += 1
			if matrica[i][j] == 'o':
				poz = i
				if br > 0:
					for k in range(poz - br, poz):
						res[k][j] = '*'
				res[poz][j] = 'o'
				br = 0
	for i in range(n):
		for j in range(m):
			if res[i][j] == '':
				res[i][j] = '.'
			print(res[i][j], end='')
		print()
for _ in range(int(input())):
	resi()


for _ in range(int(input())):
	(row, col) = map(int, input().split())
	ab = []
	for p in range(row):
		kk = input()
		ab.append(kk)
	bc = [['.' for q in range(col)] for w in range(row)]
	for i in range(col):
		stone = 0
		obstacle = -1
		for j in range(row):
			if ab[j][i] == 'o':
				bc[j][i] = 'o'
				if stone > 0:
					k = j
					while stone > 0:
						k -= 1
						bc[k][i] = '*'
						stone -= 1
			elif ab[j][i] == '*':
				stone += 1
		if stone > 0:
			k = row
			while stone > 0:
				k -= 1
				bc[k][i] = '*'
				stone -= 1
	for r in bc:
		for pp in r:
			print(pp, end='')
		print()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = []
	for _ in range(n):
		s += [list(input())]
	for i in range(m):
		e = -1
		for j in range(n - 1, -1, -1):
			if s[j][i] == '.':
				if e == -1:
					e = j
			elif s[j][i] == 'o':
				e = -1
			elif s[j][i] == '*':
				if e == -1:
					pass
				else:
					s[j][i] = '.'
					s[e][i] = '*'
					e -= 1
	for chr in s:
		for ch in chr:
			print(ch, end='')
		print()


for t in range(int(input())):
	(n, m) = map(int, input().split())
	num_list = []
	for i in range(n):
		a = list(input())
		num_list.append(a)
	sec = [list(i) for i in zip(*num_list)]
	for i in sec:
		if '*' not in i:
			continue
		fir = n - 1
		for j in range(n - 1, -1, -1):
			if i[j] == 'o':
				fir = j - 1
			elif i[j] == '*':
				(i[j], i[fir]) = (i[fir], i[j])
				fir -= 1
	for i in range(n):
		for j in range(m):
			print(sec[j][i], end='')
		print()


def pm(a):
	for i in range(len(a)):
		for j in range(len(a[i])):
			print(a[i][j], end='')
		print()
t = int(input())
for ii in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		b = str(input())
		bb = []
		for j in b:
			bb.append(j)
		a.append(bb)
	for i in range(m):
		p = n - 1
		for j in range(n - 1, -1, -1):
			if a[j][i] == '*':
				a[j][i] = '.'
				a[p][i] = '*'
				p -= 1
			elif a[j][i] == 'o':
				p = j - 1
			else:
				p += 0
	pm(a)


n = int(input())
for i in range(n):
	strng = []
	(f, b) = map(int, input().split())
	for c in range(f):
		strng.append(list(map(str, input())))
	for k in range(b):
		a = f - 1
		j = 0
		while a >= 0:
			if strng[a][k] == '.':
				j += 1
			elif strng[a][k] == '*' and j != 0:
				strng[a + j][k] = '*'
				strng[a][k] = '.'
			elif strng[a][k] == 'o':
				j = 0
			a -= 1
	for w in strng:
		for c in w:
			print(c, end='')
		print()


num = int(input())
result = []
for i in range(num):
	(r, c) = [int(x) for x in input().split()]
	all_rows = []
	new_rows = []
	for j in range(r):
		all_rows.append(input())
		new_rows.append(['.'] * c)
	for k in range(c):
		stone_number = 0
		for j in range(r):
			if all_rows[j][k] == '*':
				stone_number += 1
			if all_rows[j][k] == 'o':
				new_rows[j][k] = 'o'
				for l in range(stone_number):
					new_rows[j - l - 1][k] = '*'
				stone_number = 0
			if j == r - 1:
				for l in range(stone_number):
					new_rows[j - l][k] = '*'
				stone_number = 0
	result.append(new_rows)
for res in result:
	for row in res:
		for (cc, col) in enumerate(row):
			if cc == len(row) - 1:
				print(col)
			else:
				print(col, end='')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = [[x for x in input()] for i in range(n)]
	for i in range(m):
		count = 0
		for j in range(n):
			if lst[j][i] == '*':
				count += 1
				lst[j][i] = '.'
			if j + 1 >= n or lst[j + 1][i] == 'o':
				for k in range(count):
					lst[j - k][i] = '*'
				count = 0
	for j in range(n):
		for i in range(m):
			print(lst[j][i], sep='', end='')
		print()


t = int(input())
while t > 0:
	(m, n) = list(map(int, input().split(' ')))
	grid = []
	for i in range(m):
		grid.append(list(input()))
	for j in range(n):
		last = m - 1
		for i in range(m - 1, -1, -1):
			c = grid[i][j]
			if c == 'o':
				last = i - 1
			elif c == '*':
				(grid[i][j], grid[last][j]) = (grid[last][j], grid[i][j])
				last -= 1
	for i in range(m):
		for j in range(n):
			print(grid[i][j], end='')
		print()
	t -= 1


import sys
from collections import Counter
input = sys.stdin.readline

def get(a):
	b = ['o'] + a + ['o']
	ss = ''.join(b)
	p = ss.split('o')
	res = []
	for s in p:
		cnt = Counter(s)
		s_ok = '.' * cnt['.'] + '*' * cnt['*']
		res.append(s_ok)
	return list('o'.join(res))[1:-1]

def solve():
	(n, m) = map(int, input().split())
	a = [[0 for j in range(m)] for i in range(n)]
	for i in range(n):
		s = input()
		for j in range(m):
			a[i][j] = s[j]
	res = []
	for j in range(m):
		col = []
		for i in range(n):
			col.append(a[i][j])
		res.append(get(col))
	for j in range(m):
		for i in range(n):
			a[i][j] = res[j][i]
	for i in range(n):
		for j in range(m):
			print(a[i][j], end='')
		print()
tst = int(input())
for tt in range(tst):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	grid = [[0 for i in range(m)]]
	for row in range(n):
		temp = input()
		rowArr = []
		for col in range(m):
			if temp[col] == '.':
				rowArr.append(0)
			elif temp[col] == '*':
				rowArr.append(1)
			else:
				rowArr.append(-1)
		grid.append(rowArr)
	for col in range(m):
		for row in range(1, n + 1):
			if grid[row][col] != -1:
				grid[row][col] += max(grid[row - 1][col], 0)
				grid[row - 1][col] = min(0, grid[row - 1][col])
		r = n
		temp = ''
		while r != 0:
			if grid[r][col] == -1:
				temp += 'o'
				r -= 1
			elif grid[r][col] == 0:
				temp += '.'
				r -= 1
			else:
				temp += '*' * grid[r][col]
				r -= grid[r][col]
		for row in range(1, n + 1):
			grid[row][col] = temp[n - 1 - (row - 1)]
	for i in range(1, len(grid)):
		print(''.join(grid[i]))


def printGrid(grid):
	for i in range(len(grid)):
		print(''.join(grid[i]))

def solution(grid):
	(r, c) = (len(grid), len(grid[0]))
	for i in range(r - 1, -1, -1):
		for j in range(c - 1, -1, -1):
			if grid[i][j] == '*':
				grid[i][j] = '.'
				k = i
				while k + 1 < r and grid[k + 1][j] == '.':
					k += 1
				grid[k][j] = '*'
	printGrid(grid)

def main():
	t = eval(input())
	for _ in range(t):
		(n, m) = input().split()
		(n, m) = (int(n), int(m))
		grid = []
		for _ in range(n):
			string = input()
			lst = [s for s in string]
			grid.append(lst)
		solution(grid)
main()