Happy strings

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk prepared \(n\) happy strings \(s_i\) for Marichka. As you know, a string is happy if it consists only of the characters 4 and 7.

A string that contains 44 or 77 is hyperhappy. Hyperhappiness is dangerous, it can attract hyperhappy-seekers from the hyperuniverse if the hyperhappy string ends up in Marichka’s hands.

Marichka asked Zenyk to hand her the string obtained by concatenating the strings \(s_x\) and \(s_y\). To protect his hyperhappy-seeker-attracting beloved, Zenyk will delete all pairs of 44 and 77 from the string before handing it to Marichka. It can be shown that the result does not depend on the order in which the deletions are performed.

There are countless Marichkas in the hyperuniverse. Each has her own Zenyk. Each Zenyk has his own Marichka. We are interested to know — what will be the length of the string in the hands of each Marichka. The Algotester system does not work very well with infinite output yet, so answers from \(q\) worlds are enough for us.

Input

The first line of the input data contains a single integer \(n\) — the number of strings Zenyk prepared for Marichka.

Each of the next \(n\) lines contains exactly one non-empty string of characters 4 and 7.

The next line contains a single integer \(q\) — the number of worlds for which the answer needs to be obtained.

Each of the next \(q\) lines contains a pair of numbers \(x\) and \(y\) separated by a space — Marichka’s query in the corresponding world.

Output

Print \(q\) lines, with a single integer in the \(i\)-th line — the length of the string in Marichka’s hands in the \(i\)-th world.

Constraints

\(1 \le n, \ q \le 10^5\),

\(1 \le x_i, \ y_i \le n\),

The total length of all given strings does not exceed \(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

World 1: 47.

World 2: 4447 \(\rightarrow\) 47.

World 3: 474474 \(\rightarrow\) 4774 \(\rightarrow\) 44 \(\rightarrow\) empty string.