Sylv học toán khá yếu, cậu ta còn không phân biệt được các dấu ngoặc trong 1 phép toán đã đúng logic chưa. Với chục năm học toán của mình, bạn hãy giúp Sylv kiểm tra xem 1 chuỗi ngoặc có đúng logic không nhé.

Với 1 chuỗi ngoặc bao gồm các kí tự có trong "{} [] ()", chuỗi ngoặc thường được đảm bảo ko có ngoặc nhọn nào bên trong ngoặc vuông/tròn, và không có ngoặc vuông nào nằm trong ngoặc tròn. Các dấu mở ngoặc và đóng ngoặc theo đúng trật tự. (30% test chỉ chứa các dấu ngoặc tròn).

Input:

• Dòng đầu tiên là số nguyên \(t (t \le 10)\) ứng với số bộ test.
• t dòng tiếp theo, mỗi dòng là 1 xâu kí tự chỉ chứa các dấu ngoặc.

Output:

• Với mỗi test, in ra \(Dung\) nếu xâu kí tự thỏa mãn đúng logic yêu cầu đề bài, in \(Sai\) với trường hợp ngược lại.

Example

Input 1

2
()()
(()

Output 1

Dung
Sai

Input 2

2
([]())
{[()]}

Output 2

Sai
Dung