import io import sys from collections import defaultdict, deque, Counter from itertools import permutations, combinations, accumulate from heapq import heappush, heappop from bisect import bisect_right, bisect_left from math import gcd import math _INPUT = """\ 6 2 2 .. .. 2 2 .# #. 9 7 ....... .#####. .####.. .####.# .####.. .#...#. .#.#.#. .#.#.#. ...#... """ def Dijkstra(G,s): done=[False]*len(G) inf=10**20 C=[inf]*len(G) C[s]=0 h=[] heappush(h,(0,s)) while h: x,y=heappop(h) if done[y]: continue done[y]=True for v in G[y]: if C[v[1]]>C[y]+v[0]: C[v[1]]=C[y]+v[0] heappush(h,(C[v[1]],v[1])) return C def input(): return sys.stdin.readline()[:-1] def solve(test): H,W=map(int, input().split()) S=[input() for _ in range(H)] G=[[] for _ in range(H*W)] def idx(i,j): return i*W+j for i in range(H): for j in range(W): if S[i][j]=="#": continue for dx,dy in [(0,1),(0,-1)]: ni,nj=i+dx,j+dy if 0<=ni