Напишіть програму, яка знаходить всі розв'язки задачі про ~n~ ферзів. Прочитати постановку цієї задачі можна, наприклад, у вікіпедії.

Вхідні дані

В єдиному рядку задане єдине число ~n~ (~1\leqslant n\leqslant 12~) – розмір дошки.

Результати

Виведіть спочатку всі знайдені розміщення, наприкінці їх кількість (символ-у-символ дотримуючись описаного далі формату).

Кожне окреме розміщення, де ~n~ ферзів не б'ють один одного, слід виводити окремим рядком такого вигляду: спочатку позначку вертикалі 'a' (саму букву, без лапок), потім число, що означає, в якій горизонталі розміщено ферзя у цій вертикалі 'a', спочатку позначку 'b' та номер горизонталі ферзя у вертикалі 'b', і так далі; все це в один рядок без пробілів чи будь-яких інших роздільників. Якщо ~10\leqslant n\leqslant 12~, деякі з номерів горизонталей виявляться одноцифрові, деякі двоцифрові; так і виводити; зокрема, для ~n=10~ першим з рядків відповіді повинно бути a1b3c6d8e10f5g9h2i4j7. Всі ці рядки, що описують можливі розміщення ферзів, обов'язково повинні бути впорядковані саме так, як виходить при класичному порядку перебору, а саме: в першу чергу за номером горизонталі у вертикалі 'a', при однаковості цих номерів – за номером горизонталі у вертикалі 'b', і так далі. (При ~n\leqslant 9~ це збігається також зі стандартним словниковим порядком рядків, але при ~n\geqslant 10~ це не так; який рядок повинен бути першим при ~n=10~, вже наведено.)

Наприкінці повинен бути ще один рядок, вигляду «(totally ...)» (без лапок), де замість трикрапки слід записати кількість знайдених розміщень.

Приклади

Вхід

1

Результат

a1
(totally 1)

Вхід

2

Результат

(totally 0)

Вхід

4

Результат

a2b4c1d3
a3b1c4d2
(totally 2)

Вхід

6

Результат

a2b4c6d1e3f5
a3b6c2d5e1f4
a4b1c5d2e6f3
a5b3c1d6e4f2
(totally 4)