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

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\) пустий рядок.