Mutation

The DNA of a person is written as one long string over the letters A, C, G, and T.

Some diseases are known to be linked to a contiguous substring of that string. If the DNA contains a particular string as a substring, the chance of having the disease is high. Such a string is called a marker.

Markers mutate, so looking for the marker itself is not enough to find the marker linked to a disease.

A marker mutates like this.

• Split the marker into three parts, left to right. The first part and the third part are allowed to be empty.
• Reverse the middle part.

For the marker AGGT there are six possible results: GAGT, GGAT, TGGA, AGGT, ATGG, AGTG.

Given the DNA of a person and a marker, write a program that counts how many times the marker and its mutations appear in the DNA.

Occurrences are allowed to overlap. For example, if the DNA is ATGGAT and the marker is AGGT, the answer is 3, because ATGG, TGGA, and GGAT each appear once.

The first line contains the number of test cases $T$.

Each test case takes three lines. The first line contains the length of the DNA string $n$ and the length of the marker $m$, separated by a space ($1 \le n \le 1{,}000{,}000$, $1 \le m \le 100$). The second line contains the DNA, and the third line contains the marker.

Both the DNA and the marker consist only of the letters A, C, G, and T.

For each test case, print on its own line a single integer, the number of times the marker and its mutations appear in the DNA.

If neither the marker nor any of its mutations appears in the DNA, print 0.