Dãy ngoặc đúng là một chuỗi các ký tự ngoặc mở \((\) và ngoặc đóng \()\) được sắp xếp sao cho mỗi ngoặc mở đều có một ngoặc đóng tương ứng và ngoặc đóng không xuất hiện trước ngoặc mở tương ứng của nó. Ngoặc mở và ngoặc đóng phải đúng theo thứ tự, tức là mỗi ngoặc mở phải được đóng bởi ngoặc đóng sau nó và không được đóng bởi ngoặc đóng khác.

Ví dụ về các dãy ngoặc đúng:

• \(()\): Dãy ngoặc đúng đơn giản với một cặp ngoặc.
• \(()()\): Dãy ngoặc đúng với hai cặp ngoặc không lồng nhau.
• \((())\): Dãy ngoặc đúng với hai cặp ngoặc lồng nhau.
• \(()()()\): Dãy ngoặc đúng với ba cặp ngoặc không lồng nhau.
• \((()())\): Dãy ngoặc đúng với ba cặp ngoặc, trong đó có một cặp ngoặc lồng nhau.

Cho \(n\), hãy tìm tất cả các dãy ngoặc đúng có độ dài \(2n\).

Input

• Một số nguyên dương \(n \le 12\)

Output

• Dòng đầu ghi một số nguyên dương cho biết số lượng dãy ngoặc đúng tìm được.
• Những dòng tiếp theo, mỗi dòng ghi một dãy ngoặc đúng theo thứ tự như ví dụ.

Constraints

• \(1 \le n \le 12\)

Example

Sample input

4

Sample output

14
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()