D. Огромные строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано n строк s1, s2, ..., sn, состоящих из символов 0 и 1. Далее m раз создается новая строка как конкатенация уже имеющихся. Формально, на i-м шаге конкатенация saisbi записывается в новую строку sn + i (нумерация шагов ведется с 1). После каждой операции вам нужно найти максимальное положительное целое число k такое, что в полученной строке встречаются все возможные строки из 0 и 1 длины k (а таких различных строк 2k) как подстроки. Если такого k не существует, выведите 0.

Входные данные

Первая строка содержит одно целое число n (1 ≤ n ≤ 100) — количество строк. Следующие n строк содержат строки s1, s2, ..., sn (1 ≤ |si| ≤ 100) по одной в строке. Суммарная длина строк не превосходит 100.

Следующая строка содержит число m (1 ≤ m ≤ 100) — количество операций. За ней следуют m строк, содержащих по два целых числа ai и bi (1 ≤ ai, bi ≤ n + i - 1) — номера строк, образующих новую строку sn + i.

Выходные данные

Выведите m строк, содержащие по одному целому числу — ответы на запросы после операций.

Пример
Входные данные
5
01
10
101
11111
0
3
1 2
6 5
4 4
Выходные данные
1
2
0
Примечание

В первой операции создается строка "0110". Для k = 1 две возможные бинарные строки длины k — это "0" и "1", они обе являются подстроками новой строки. Для k = 2 и больше существуют строки длины k, не встречающиеся в получившейся строке (для k = 2 такая строка — это "00"). Поэтому ответ равен 1.

Во второй операции создается строка "01100". Теперь присутствуют все строки длины k = 2.

В третьей операции создается строка "1111111111". В ней нет нулей, поэтому ответ равен 0.