DNA Motif Occurrence Counter

You are given a DNA sequence and a motif. Your task is to determine how many times the motif appears in the DNA sequence as a contiguous subsequence.

The input starts with an integer T which represents the number of test cases. Each test case consists of two lines: the first line contains the DNA sequence and the second line contains the motif. Note that the DNA sequence and the motif consist only of uppercase letters from the set \(\{A, C, G, T\}\).

Your program should output the count of motif occurrences for each test case, with each result on a new line.

inputFormat

The first line contains an integer T denoting the number of test cases. For every test case, there are two subsequent lines. The first line contains a DNA sequence and the second line contains the motif.

outputFormat

For each test case, output a single integer on a new line representing the number of times the motif occurs in the DNA sequence.## sample

3
ACGTACGTAC
AC
CTGACTGACTGAC
CTGA
AAAAAA
AA

3
3
5