C++ :

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

string _a, _b;

long long dp[30][30][30][30];

long long DP(int l, int r, int a, int b) { // cout << l << " " << r << " " << a << " " << b << endl;
	// if (l > r) return 1;

	if (dp[l][r][a][b] != -1) return dp[l][r][a][b];

	if (_a[l] != _b[b]) return dp[l][r][a][b] = 0;

	if (l == r ) return dp[l][r][a][b] = 1;

	long long res = DP(l+1, r, a, b-1) * 2;
	
	for (int k=l+1; k<r; k++) {
		res += DP(l+1, k, a, a+k-l-1) * DP(k+1, r, a+k-l, b-1);
	}
	return dp[l][r][a][b] = res;
}

int main () {
	int T;
	cin >> T;
	while (T--) {
		cin >> _a >> _b;

		memset(dp, -1, sizeof(dp));
		cout << DP(0, _a.size()-1, 0, _b.size()-1) << endl;
	}
	return 0;
}