Маршрут с одним сносом

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

Ты идёшь из северо‑западного угла (верхняя левая клетка) в юго‑восточный (нижняя правая клетка). За весь путь ты можешь снести стену ровно в одном квартале (или не сносить вообще), и после этого этот квартал становится проходимым.

Переходить можно только между клетками с общей стороной.

Нужно узнать минимальное число шагов (переходов между соседними клетками), чтобы дойти до финиша. Если это невозможно даже с одним сносом, выведи -1.

Формат ввода

В первой строке дано число t — количество наборов данных.

Далее идут t наборов данных. Каждый набор задан в следующем формате:

В первой строке два числа R и C — число строк и столбцов. Дальше идут R строк по C символов:

• . — свободный квартал,
• # — стена.

Гарантируется, что в первой и последней клетке стоит ..

Формат вывода

Для каждого набора данных выведите одно целое число — минимальное число шагов, либо -1. Ответы выводите в отдельных строках.

Ограничения

• 1 ≤ t ≤ 4
• 1 ≤ R ≤ 1000
• 1 ≤ C ≤ 1000
• Сумма значений R * C по всем наборам данных не превышает 10^6.

Пример

Ввод:

3
1 1
.
1 2
..
2 2
.#
#.

Вывод:

0
1
2