Công ty LDK đang sản xuất robot vận chuyển hàng hóa tự động trên mặt phẳng. Để làm việc đó, công ty tiến hành huấn luyện các robot trên một địa hình phẳng được chia thành một lưới các ô vuông gồm ~3~ dòng (đánh số từ ~1~ đến ~3~ theo chiều từ trên xuống dưới) và ~n~ cột (đánh số từ ~1~ đến ~n~ theo chiều từ trái sang phải). Ô giao giữa dòng ~i~, cột ~j~ được gọi là ô ~(i, j)~ và thuộc một trong 5 loại dưới đây:

Ví dụ một địa hình kích thước ~3 \times 6~.

~1)~ Ô xuất phát, kí hiệu là S~;~
~2)~ Ô kết thúc, kí hiệu là T~;~
~3)~ Ô trống, kí hiệu là .~;~
~4)~ Ô cấm, kí hiệu là #~;~
~5)~ Ô kém chất lượng, kí hiệu là *~.~

Một đường thử nghiệm cho robot là một dãy liên tiếp các ô chung cạnh, bắt đầu tại ô S, kết thúc tại một ô T và thỏa mãn các điều kiện sau:

• Không chứa ô cấm~;~
• Không chứa ô S, T nào khác~;~
• Số ô kém chất lượng không quá một ô.

Yêu cầu: Cho biết thông tin các ô của lưới, hãy giúp công ty tìm phương án thiết kế có nhiều đường thử nghiệm nhất mà mỗi ô của lưới thuộc không quá một đường thử nghiệm.

Lưu ý: Đọc input, output từ stdin/stdout (không phải từ file như trong đề)

Dữ liệu

Dòng thứ nhất chứa một số nguyên ~n;~

Dòng thứ ~i~ trong số ~3~ tiếp theo chứa xâu mô tả thông tin các ô liên tiếp trên hàng thứ ~i~ của lưới.

Kết quả

Ghi ra một số nguyên là số đường thử nghiệm nhiều nhất tìm được.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~n \le 100~, không có ô kém chất lượng và các ô thuộc hàng ~2~ và hàng ~3~ của địa hình đều là ô cấm~;~
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~n \le 100~ và địa hình không có ô kém chất lượng~;~
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~n \le 10^5~ và các ô thuộc hàng 3 của địa hình đều là ô cấm~;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài thỏa mãn điều kiện: ~n \le 10^5~ và không có điều kiện gì thêm trên địa hình.

Sample Input

10
T.*S..##S#
**###T#T.S
.*S.*.##T#

Sample Output

3