Hôm nay bin9638 đang đánh bài ma sói với algorit và WuTan, vì đã quá chán luật ma sói cũ nên cậu đã tự nghĩ ra luật mới.

Bộ bài ma sói gồm một số lá, gồm những lá như sau:

• Lá dân làng : được kí hiệu là "D", trong bộ bài có thể chứa nhiều lá dân làng.

• Lá ma sói: được kí hiệu là "M", trong bộ bài có thể chứa nhiều lá ma sói.

• Lá thợ săn: được kí hiệu là "T", trong bộ bài có thể chứa nhiều lá thợ săn.

• Lá phù thủy: được kí hiệu là "P", trong bộ bài có thể chứa nhiều lá phù thùy.

• Lá chiến thắng: được kí hiệu là "#", trong bộ bài chỉ chứa duy nhất MỘT lá chiến thắng.

Trong mỗi lượt chơi:

• Chỉ được rút MỘT lá ở đầu hoặc cuối bộ bài.

• Có thể sử dụng các lá bài thợ săn đang có trên tay, sau khi dùng một lá thợ săn, người chơi sẽ bỏ đồng thơi một lá thợ săn và một lá ma sói xuống (không dược bỏ lại vào bộ bài).

• Có thể sử dụng các lá bài phù thùy đang có trên tay, sau khi dùng một lá phù thùy người chơi sẽ bỏ đồng thời một lá phù thùy và một lá dân làng xuống (không được bỏ lại vào bộ bài).

• Người chơi có thể sử dụng tùy ý số lượng lá bài mình đang có, tuy nhiên chỉ được rút một lá bài duy nhất. Không nhất thiết phải làm theo thứ tự, người chơi có thể rút bài trước rồi sử dụng các lá bài, hoặc sử dụng các lá bài trước, rồi sau đó mới rút bài.

• Khi kết thúc một lượt chơi, nếu số lá ma sói người chơi đang có trên tay lớn hơn hẳn số lá dân làng người chơi đang có thì sói sẽ ăn hết dân, lúc này trò chơi kết thúc và người chơi sẽ thua cuộc.

• Người chơi sẽ chiến thắng nếu rút được lá chiến thắng.

Tuy là người đặt ra luật của trò chơi này, nhưng bin9638 không biết cách chơi như thế nào để chiến thắng, đồng thời sau khi chiến thắng, anh ấy muốn chênh lệch giữa số lá dân làng còn lại trên tay và số lá ma sói còn lại trên tay là nhỏ nhất.

Hãy giúp bin9638 chơi một cách tối ưu nhất nhé!

Input

• Dòng đầu tiên là số ván bài \(Q\).
• \(Q\) dòng tiếp theo mỗi dòng là một xâu \(S\) miêu tả bộ bài.

Input

• Gồm \(Q\) dòng với mỗi dòng là kết quả của ván đấu tương ứng, nếu bin9638 thua thì ghi "LOSE", ngược lại ghi số lá bài chênh lệch bé nhất sau khi thắng.

Constrains

• \(Q \leq 50\)
• \(|S| \leq 2000\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(|S| \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(|S| \leq 100\).
• Subtask \(3\) (\(30\%\) số điểm): \(|S| \leq 1000\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
M#DMMT
MD#DM
MM#DDDPPT
DDDP#DDDD
TPMD#MM

0
LOSE
0
2
0