У Фермера Джона є \(N\) подарунків помічених числами \(1\ldots N\) для його \(N\) корів, також помічених числами \(1\ldots N\) (\(1\le N\le 18\)) Кожна корова має список переваг, який є перестановкою з усіх \(N\) подарунків, так що корова віддає перевагу подарунку, який з'явився у списку раніше за подарунок, який з'явився у списку пізніше.

ФД через лінощі просто призначив корові \(i\) подарунок \(i\) для всіх \(i\). Тепер корови зібралися та вирішили перепризначити подарунки так, щоб у кожної корови або залишився початковий подарунок, або він був замінений на більш улюблений подарунок.

Є також додаткове обмеження: подарунок може бути перепризначений корові, якщо він спочатку був призначений корові такого ж типу (Holstein або Guernsey)). Задано \(Q\) (\(1\le Q\le \min(10^5,2^N)\))довжин \(N\) рядків порід для кожної їх обчисліть кількість перепризначень, відповідних їй.

Формат вхідних даних

Перший рядок містить \(N\).

Кожен із наступних \(N\) рядків містить список переваг однієї корови. Гарантується, що кожен рядок є перестановкою \(1\dots N\).

Наступний рядок містить \(Q\).

Кожен із наступних \(Q\) рядків містить рядок порід, кожен має \(N\) символів довжину і складається лише з символів G і H. Ніякий рядок порід не з'явиться більше ніж один раз.

Формат вихідних даних

Для кожного рядка порід виведіть в окремому рядку кількість перестановок, що відповідають їй.

Приклад вхідних даних

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG

Приклад вихідних даних

2
1
1
2
2

У цьому прикладі, для першого рядка порід можливі два призначення:

• Оригінальне призначення:

  корова \(1\) отримала подарунок \(1\),

  корова \(2\) отримала подарунок \(2\),

  корова \(3\) отримала подарунок \(3\),

  корова \(4\) отримала подарунок \(4\).

• Корова \(1\) отримала подарунок \(1\),

  корова \(2\) отримала подарунок \(3\),

  корова \(3\) отримала подарунок \(2\),

  корова \(4\) отримала подарунок \(4\).

  Для другого рядка порід єдине можливе призначення – оригінальне.

  ОЦІНЮВАННЯ:

  • Для \(T = 2, \ldots, 13\), тест \(T\) задовольняє \(N = T + 4\).
  • У тестах 14-18 \(N = 18\).

  Автор: Benjamin Qi