need help with my java howework assignment. we have only discussed loops and arrays for this assignment. also must have all code in the main block only. cant have any sub-mains since we havent discussed that in class yet. also we can not use any API funcitons. have added the assignment via attachment for understanding of the problem.

Program 1 (Loop statement, Array): Humans DNA is a sequence of four bases, A, C, G, T. Lets assume that some diseases are related to a particular sequence. We call the special sequence marker. It means that one has higher probability to have the disease if his/her DNA sequence includes the marker. The marker could have mutations. The mutation rule is that any sub-sequence of the marker can change the order. For example, the marker is AGGT. There are 6 different sub-sequences and changed orders as follows.

Sub-sequence Mutations

AGGT => TGGA

AGGT => GAGT

AGGT => AGGT

AGGT => AGTG

AGGT => GGAT

AGGT => ATGG

Totally, there are 6 markers including original (Green) and mutated (Blue) things.

AGGT, TGGA, GAGT, AGGT, AGTG, GGAT, ATGG

Make a program that count how many time the markers are expressed in a given sequence. Note that the expression could be overlapped. For example, if a given sequence is ATGGAT and a original markers sequence is AGGT, the answer is 3 because ATGG, TGGA, GGAT are expressed in the given human sequence like ATGGAT, ATGGAT, ATGGAT. Input:

Number of test cases

Length of test DNA and original marker

Test DNA sequence

Markers sequence

Output

Number of expression time of makers for each test case

Example

Input:

2

6 4

ATGGAT

AGGT

6 4

ATGGAT

AGCT

Output

3

0