Định nghĩa khái niệm dãy ngoặc đúng dưới dạng đệ quy như sau:

1. () là dãy ngoặc đúng
2. C là dãy ngoặc đúng nếu C = (A) hay C = AB với A, B là các dãy ngoặc đúng.
3. Ví dụ dãy ngoặc đúng: (), (()), ()(), (())()
4. Ví dụ dãy ngoặc sai: )(, ((((, ()((, )))), )()(

Bạn hãy viết chương trình liệt kê tất cả các dãy ngoặc đúng có chiều dài ~n~ (~n~ chẵn)

Input

• Là số nguyên ~n~ (~n~ chẵn, ~2 ≤ n ≤ 20~)

Output

với ~m~ là số lượng các dãy ngoặc đúng có chiều dài ~n~

• Trong m dòng đầu tiên, mỗi dòng liệt kê một dãy ngoặc đúng chiều dài ~n~. Các dãy được liệt kê theo thứ tự từ điển: '(' nhỏ hơn ')'.
• Dòng cuối cùng là số ~m~

Sample

Input #1

4

Output #1

(())
()()
2

Problem source: CLB Lập Trình PTIT