Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận ~n \times m~, ô ở hàng ~i~ cột ~j~ được gọi là ô ~(i,j)~.

Công việc này chưa bao giờ là dễ dàng. Một vài ô đã bị địch cài bom và không biết khi nào sẽ phát nổ. Bạn chỉ biết rằng loại bom này có sức công phá là ~r~, có nghĩa là nếu bom ở ô ~(i,j)~, khi nó phát nổ thì các ô ~(u,v)~ thỏa mãn ~|i-u| + |j-v| \le r~ sẽ bị tàn phá (ô ~(i,j)~ và ~(u,v)~ đều nằm trong bảng). Những ô ~(u,v)~ như vậy gọi là những ô bị ảnh hưởng bởi bom.

Đây là tài liệu mật, tất nhiên chỉ huy của bạn không muốn nhận một sự rủi ro nào, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. Biết rằng bạn có thể đi sang ~4~ ô kề cạnh với ô đang đứng và mỗi ô ~(i,j)~ sẽ được miêu tả bằng một kí tự như sau:

• ~c(i,j) = .~, nếu đây là một ô bình thường có thể đi.
• ~c(i,j) = *~, đây là vùng nguy hiểm tuyệt đối không được đi vào.
• ~c(i,j) = +~, đây là ô có bom, như đã nói, các ô nằm cách ô này khoảng cách không quá ~r~ (kể cả chính nó) sẽ không thể đi vào.
• ~c(i,j) = S~, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
• ~c(i,j) = T~, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.

Input

• Dòng đầu tiên gồm ~3~ số nguyên ~n,m,r~, miêu tả kích thước bảng và vùng ảnh hưởng của bom.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.
• Dữ liệu luôn đảm bảo ô chứa kí tự ~S~ và ~T~ không bị ảnh hưởng bởi ô chứa bom nào.

Output

• In ra một dòng là đường đi ngắn nhất từ đơn vị tới sở chỉ huy sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. Nếu không có một đường đi nào như vậy, in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 1000~
• ~0 \le r \le 1000~

Subtask

• ~20\%~ số điểm: Không có ô nào có ~c(i,j) = *~ hoặc ~c(i,j) = +~.
• ~20\%~ số điểm: ~r = 0~.
• ~30\%~ số điểm: ~n,m \le 100~.
• ~30\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input 1:

3 4 1
S...
....
...T

Output 1:

5

Input 2:

3 4 0
S.+T
*.*.
*...

Output 2:

7

Input 3:

4 4 1
S..*
*...
+.*.
.T..

Output 3:

8