See Problem N for PDF statements.

You are given a tree with nodes. A character or is written on each node. You are also given queries. For each query, you need to calculate the number of different palindromic substrings of the string obtained from the simple path from node to node .

We say two strings and are different if their lengths are different or there exists at least one position satisfying . A palindromic string is a string that reads the same forward or backward.

输入描述:

The first line of the input contains an integer  (), indicating the number of test cases.

For each test case, the first line contains two integers  (), indicating the number of nodes and the number of queries.

The second line contains a string of length  consisting of  or , indicating the characters written on nodes from  to .

Each of the following  lines contains two integers  (), indicating an edge connecting nodes  and . It is guaranteed that these edges form a tree.

Each of the following  lines contains two integers  (), indicating a query with nodes  and .

It is guaranteed that  and  over all test cases.

输出描述:

For each query, output the answer in a single line.

1
5 5
01110
1 2
1 3
2 4
2 5
1 1
1 2
3 4
3 5
4 5

1
2
4
4
3