Do you know Just Odd Inventions Co., Ltd? The business of this company is doing "just odd inventions." Here we shall abbreviate its name, and call it the JOI Company.

Recently, the JOI Company is faced with a serious decline in its profitability by doing just odd inventions only. It is planning to start a new business. The plan is to sell liquid containing RNA chains. An RNA chain is considered as a string consisting of ~4~ characters A, G, C, U. For its business, the JOI Company prepares ~N~ chains of RNA.

The JOI Company will accept an order of RNA chains from customers in the following form:

• A customer chooses two strings ~P~, ~Q~. Then, among RNA chains prepared by the JOI Company, it sells strings whose first ~|P|~ characters are ~P~ and last ~|Q|~ characters are ~Q~. Here, ~|P|~, ~|Q|~ are the length of ~P~, ~Q~, respectively.

How many RNA chains prepared by the JOI Company match the conditions of orders from customers?

Given the information on RNA chains prepared by the JOI Company and orders from customers, write a program which calculates the number of RNA chains prepared by the JOI Company which match the conditions of orders from customers.

Input Specification

Read the following data from the standard input.

• The first line of input contains two space separated integers ~N~, ~M~. This means the JOI Company prepares ~N~ chains of RNA, and there are ~M~ orders from customers.
• The ~i~-th line (~1 \le i \le N~) of the following ~N~ lines contains a string ~S_i~, which is the ~i~-th RNA chain prepared by the JOI Company.
• The ~j~-th line (~1 \le j \le M~) of the following ~M~ lines contains two space separated strings ~P_j~, ~Q_j~. This means, in the ~j~-th order, the customer chooses two strings ~P_j~, ~Q_j~.

Output Specification

The output consists of ~M~ lines. The ~j~-th line (~1 \le j \le M~) contains an integer, the number of RNA chains prepared by the JOI Company which match the condition of the ~j~-th order.

Constraints

All input data satisfy the following conditions.

• ~1 \le N \le 100\,000~.
• ~1 \le M \le 100\,000~.
• Each string consists of ~4~ characters A, G, C, U.
• ~1 \le |S_i| \le 100\,000~ (~1 \le i \le N~).
• ~1 \le |P_j| \le 100\,000~ (~1 \le j \le M~).
• ~1 \le |Q_j| \le 100\,000~ (~1 \le j \le M~).
• ~\sum_{i=1}^N |S_i| \le 2\,000\,000~.
• ~\sum_{j=1}^M |P_j| \le 2\,000\,000~.
• ~\sum_{j=1}^M |Q_j| \le 2\,000\,000~.

Sample Input 1

2 3
AUGC
AGC
G C
AU C
A C

Sample Output 1

0
1
2

Sample Input 2

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

Sample Output 2

2
1
1