#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <random>
#include <ctime>
#include <map>
#include <set>
using namespace std;
// #define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << x << '\n'
#define lowbit(x) (x & -x)
#define debug puts("qwq");
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
	}
	template <typename T>
	inline void write(T x, char ch = '\n') {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	template <typename T>
	inline void smax(T &x, T y) {
		if (x < y) x = y;
	}
	template <typename T>
	inline void smin(T &x, T y) {
		if (x > y) x = y;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
const int N = 1e5 + 19, base = 5, mod = 1e9 + 7;
int pw[N], a[N], b[N], n, m;
char s[N], t[N];
int getvalue(char c) {
	if (c == 'A') return 1;
	if (c == 'C') return 2;
	if (c == 'G') return 3;
	return 4;
}
int gethash(int l, int r) {
	return ((a[r] - 1LL * a[l - 1] * pw[r - l + 1]) % mod + mod) % mod;
}
int gethash2(int l, int r) {
	return ((b[r] - 1LL * b[l - 1] * pw[r - l + 1]) % mod + mod) % mod;
}
int lcp(int x, int y, int r) {
	int l = 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (gethash(x, x + mid - 1) == gethash2(y, y + mid - 1)) l = mid + 1;
		else r = mid;
	}
	return l - 1;
}
int check(int x) {
	int r = x + m - 1, y = 1;
	for (int i = 1; i <= 3; ++i) {
		int t = lcp(x, y, m - y + 1);
		x += t + 1;
		y += t + 1;
		if (y > m)return 1;
	}
	return gethash(x, r) == gethash2(y, m);
}
void solve() {
	scanf("%s%s", s + 1, t + 1);
	n = strlen(s + 1), m = strlen(t + 1);
	for (int i = 1; i <= n; ++i) {
		a[i] = (1LL * a[i] * 5 + getvalue(s[i])) % mod;
	}
	for (int i = 1; i <= m; ++i) {
		b[i] = (1LL * b[i] * 5 + getvalue(s[i])) % mod;
	}
	int ans = 0;
	for (int i = 1; i + m - 1 <= n; ++i) {
		ans += check(i);
	}
	write(ans);
}
signed main() {
	pw[0] = 1;
	for (int i = 1; i < N; ++i) pw[i] = 1LL * pw[i - 1] * 5 % mod;
	int t = read();
	while (t--) {
		solve();
	}
	return 0;
}