Even substrings

Time limit2sMemory limit512 MB

Summary

For each query listing up to 5 letters, count substrings of S in which every listed letter occurs an even number of times.

Level: Hard8 of 10
Topics: Bit manipulation, Hash map, Prefix sum
Solved: No attempts yet

Problem

You are given a string $S$ that uses only the letters a through t. Write a program that answers the following query.

k c1 c2 ... ck: print how many contiguous substrings of $S$ contain each of the letters $c_1, c_2, \dots, c_k$ an even number of times.

A letter that never appears occurs zero times, and zero is even. Substrings are identified by their start and end positions, so two equal substrings at different positions count separately. The empty substring is not counted.

Input

The first line has the number of test cases $T$ ( $1 \le T \le 5$ ).

The first line of each test case has the string $S$ . Its length is at most 100,000 and it uses only the letters a through t. The second line has the number of queries $Q$ ( $1 \le Q \le 30000$ ).

Each of the next $Q$ lines has one query in the form k c1 c2 ... ck. Here $k$ is a positive integer no greater than 5, and $c_1, c_2, \dots, c_k$ are the letters of the query. No letter appears twice in one query.

Output

For each query, print the number of substrings that satisfy it on its own line.

Examples2

Example 1

Input

1
cacca
5
3 c a b
2 c b
2 a b
3 c b a
2 a b

Expected output

Example 2
Input
```
1
a
3
1 a
1 b
5 a b c d e
```
Expected output
```
0
1
0
```