돌연변이

사람의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 나타낼 수 있다.

몇몇 질병은 DNA 문자열의 연속된 부분 문자열과 관련이 있다고 알려져 있다. DNA가 특정 문자열을 부분 문자열로 가지면 그 질병에 걸릴 가능성이 높다. 이런 문자열을 마커(marker)라고 한다.

그런데 마커는 돌연변이를 일으키므로, DNA에서 마커를 그대로 찾는 것만으로는 질병과 관련된 마커를 놓칠 수 있다.

마커의 돌연변이는 다음과 같이 일어난다.

• 마커를 앞에서부터 세 부분으로 나눈다. 첫 부분과 세 번째 부분은 비어 있어도 된다.
• 가운데 부분을 뒤집는다.

마커가 AGGT라면 GAGT, GGAT, TGGA, AGGT, ATGG, AGTG의 여섯 가지가 가능하다.

어떤 사람의 DNA 구조와 마커가 주어졌을 때, 마커와 그 돌연변이가 DNA 안에 모두 몇 번 나타나는지 세는 프로그램을 작성하라.

나타나는 위치는 서로 겹쳐도 된다. 예를 들어 DNA 구조가 ATGGAT이고 마커가 AGGT라면 답은 3이다. ATGG, TGGA, GGAT가 각각 한 번씩 나타나기 때문이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 세 줄이다. 첫 줄에 DNA 문자열의 길이 $n$과 마커의 길이 $m$이 공백으로 구분되어 주어진다 ($1 \le n \le 1{,}000{,}000$, $1 \le m \le 100$). 둘째 줄에 DNA 구조가, 셋째 줄에 마커가 주어진다.

DNA와 마커는 모두 A, C, G, T로만 이루어진 문자열이다.

각 테스트 케이스마다 마커와 그 돌연변이가 DNA 구조에 나타난 횟수를 정수 하나로 한 줄에 출력한다.

마커와 그 돌연변이가 DNA 구조 안에 한 번도 나타나지 않으면 0을 출력한다.