Given a string S of length N consisting of only lower-case English alphabets, you will be asked to process Q queries over it . In each query you will be given two lower case characters X and Y. Your task is to find out the number of such substrings of the the string S which have the characters X and Y on either of its end points, both X...Y and Y...X are considered to be valid.

Note : Substrings length should be greater than 1.

Input:
The first line of the input will contain N , the length of the string.
Next line will contain as string of length N. Next line will will contain Q , the number of queries. Then Q subsequent lines will contain two lowercase characters X and Y separated by a space.

Output:
For each query , output the answer in a separate line.

Constraints:

• \(1 \le N \le 10^6\)
• \(1 \le Q \le 10^3\)