Щасливі рядки

Limits: 2 sec., 256 MiB

Зеник підготував для Марічки $n$ щасливих рядків $s_i$. Як відомо, рядок є щасливим, якщо він складається тільки із символів 4 та 7.

Рядок, який містить в собі 44 або 77 є гіперщасливим. Гіперщастя — небезпечне, воно може приманити гіперщастешукачів із гіпервсесвіту, якщо гіперщасливий рядок опиниться в руках у Марічки.

Марічка попросила Зеника передати їй в руки рядок, отриманий конкатенацією рядків $s_x$ та $s_y$. Щоб вберегти свою гіперщастешукачоприманювальну кохану, Зеник видалить всі пари 44 та 77 із рядка перед тим як передавати його Марічці. Можна показати, що результат не залежить від того, в якому порядку виконувати видалення.

У гіпервсесвіті є безліч Марічок. В кожної є свій Зеник. В кожного Зеника є своя Марічка. Нам цікаво знати — яка буде довжина рядка в руках у кожної Марічки. Система Алготестер поки що не дуже добре працює із нескінченним виводом, тому для нас достатньо відповідей із $q$ світів.

Input

У першому рядку вхідних даних задано єдине ціле число $n$ — кількість рядків, які Зеник підготував для Марічки.

У кожному з наступних $n$ рядків задано рівно один непорожній рядок із символів 4 та 7.

У наступному рядку задано єдине ціле число $q$ — кількість світів, відповідь з яких потрібно отримати.

У кожному з наступних $q$ рядків задано пару чисел $x$ і $y$ розділених пробілом — запит Марічки у відповідному світі.

Output

Виведіть $q$ рядків, у $i$-ому рядку єдине ціле число — довжина рядка у руках Марічки у $i$-му світі.

Constraints

$1 \le n, \ q \le 10^5$,

$1 \le x_i, \ y_i \le n$,

Загальна довжина всіх заданих рядків не перевищує $5 \cdot 10^5$.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 4 7 44 474 47 3 1 2 3 5 4 4	2 2 0

Notes

Світ 1: 47.

Світ 2: 4447 $\rightarrow$ 47.

Світ 3: 474474 $\rightarrow$ 4774 $\rightarrow$ 44 $\rightarrow$ пустий рядок.