G. Падение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана матрица из $$$n$$$ строк и $$$m$$$ столбцов, каждая ячейка которой имеет один из трех типов:

  • Пустая ячейка (обозначается как «.»).
  • Камень (обозначается как «*»).
  • Препятствие (обозначается как строчная буква латинского алфавита «o»).

Каждый камень начинает падать, пока не окажется на полу (в нижней строке матрицы), в ячейке над препятствием, или в ячейке над другим камнем, который уже закончил падение. (Другими словами, все камни начинают падать и падают, пока под ними пустые ячейки.)

Просимулируйте процесс и выведите состояние матрицы после того, как все камни закончат падать.

Входные данные

В первой строке задано целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следуют сами наборы входных данных.

В первой строке каждого набора входных данных заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 50$$$) — количество строк и столбцов в матрице.

Затем следуют $$$n$$$ строк, каждая из которых содержит $$$m$$$ символов. Каждый из этих символов — «.», «*» или «o» (пустая клетка, камень и препятствие соответственно).

Выходные данные

Для каждого набора входных данных выведите матрицу из $$$n$$$ строк и $$$m$$$ столбцов, описывающую результат процесса.

Не обязательно выводить новую строку после каждого набора входных данных; в примерах из условия она выводится для наглядности.

Пример
Входные данные
3
6 10
.*.*....*.
.*.......*
...o....o.
.*.*....*.
..........
.o......o*
2 9
...***ooo
.*o.*o.*o
5 5
*****
*....
*****
....*
*****
Выходные данные
..........
...*....*.
.*.o....o.
.*........
.*......**
.o.*....o*

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

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