You are given $$$n$$$ strings, and you need to answer $$$q$$$ queries. Each query is composed of two strings $$$l_i$$$ and $$$r_i$$$. For such a query, you need to count the number of the given strings such that either it has $$$l_i$$$ as a prefix, $$$r_i$$$ as a suffix, or both (thus, a string that has $$$l_i$$$ for a prefix and $$$r_i$$$ for a suffix should be counted once).
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the number of strings. Then follow $$$n$$$ strings, each in its own line. The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$), the number of queries. Then $$$q$$$ lines follow, the $$$i$$$-th of them contains two strings $$$l_i$$$ and $$$r_i$$$. None of the strings in the input is empty.
The sum of the lengths of all strings in the input does not exceed $$$10^5$$$ (including queries). All strings consist of lowercase English alphabet letters only.
For each query, output the number of the given strings that have either the given prefix or the given suffix (or both).
3 bat eca baca 1 ba ca
3
