드릴 로봇의 미로 탈출

로봇 한 대가 $M \times N$ 격자 모양의 미로에 갇혀 있다. 각 칸은 빈 칸이거나 벽이다. 로봇은 벽이 있는 칸으로 바로 들어갈 수 없고, 미로의 바깥 경계는 매우 단단해서 미로 밖으로도 나갈 수 없다. 다만 로봇은 드릴을 가지고 있어서, 에너지를 $1$만큼 쓰면 벽 칸 하나를 빈 칸으로 바꿀 수 있고 그 뒤에 그 칸으로 들어갈 수 있다.

로봇은 주어진 시작 칸에서 출발해 목적지 칸에 도착하려고 한다. 한 번의 이동으로 로봇은 상하좌우로 인접한 칸으로 옮겨 간다. 빈 칸으로 들어가는 데에는 에너지가 들지 않지만, 벽 칸으로 들어가려면 먼저 그 벽을 뚫어야 하고 이때 에너지 $1$이 든다. 로봇에 저장된 에너지의 양은 정해져 있다.

미로의 지도와 저장된 에너지가 주어질 때, 로봇이 목적지에 도달할 수 있는지 판단하여라.

첫 번째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다. 첫 줄에는 로봇에 저장된 에너지의 양을 나타내는 정수 $k$ ($k \ge 0$)가 주어진다. 다음 줄에는 미로의 행과 열의 크기를 나타내는 두 정수 $M$과 $N$ ($1 \le M \le 500$, $1 \le N \le 500$)이 주어진다. 이어지는 $M$개의 줄에는 각각 미로의 한 행을 나타내는 정확히 $N$개의 문자가 주어진다. 문자 *는 벽을, .는 빈 칸을 뜻한다. S는 로봇의 시작 위치를, T는 목적지를 뜻한다. 미로의 한 행에 있는 각 기호는 적어도 하나의 공백 문자로 구분되어 있다.

각 테스트 케이스마다 한 줄에, 로봇이 $k$ 이하의 에너지를 써서 목적지에 도달할 수 있으면 y를, 그렇지 않으면 n을 출력한다.