Thử nghiệm robot

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:

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à . (dấu chấm);
4. Ô cấm, kí hiệu là #;
5. Ô kém chất lượng, kí hiệu là *.

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

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.

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên $n$;
• Dòng thứ $i$ trong số $3$ dòng tiếp theo chứa xâu độ dài $n$ mô tả thông tin các ô liên tiếp trên hàng thứ $i$ của lưới (gồm các kí tự S, T, ., #, *).

Dữ liệu ra

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

Ràng buộc

• $1\le n\le {10}^5$.

Subtasks

• Subtask 1 ($30\%$ số test, $30\%$ số điểm): $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;
• Subtask 2 ($30\%$ số test, $30\%$ số điểm): $n\le 100$ và địa hình không có ô kém chất lượng;
• Subtask 3 ($30\%$ số test, $30\%$ số điểm): $n\le {10}^5$ và các ô thuộc hàng $3$ của địa hình đều là ô cấm;
• Subtask 4 ($10\%$ số test, $10\%$ số điểm): $n\le {10}^5$ và không có điều kiện gì thêm trên địa hình.

Ví dụ