public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		StringBuilder out = new StringBuilder();
		init();
		while ((line = in.readLine()) != null && line.length() != 0) {
			int t = Integer.parseInt(line.trim());
			for (int i = 0; i < t; i++) {
				char[] a = in.readLine().trim().toCharArray();
				char[] b = in.readLine().trim().toCharArray();
				for (int j = 1; j <= b.length; j++)
					for (int k = 1; k <= a.length; k++)
						if (b[j - 1] == a[k - 1])
							dp[j][k] = dp[j - 1][k - 1].add(dp[j][k - 1]);
						else
							dp[j][k] = dp[j][k - 1];
				out.append(dp[b.length][a.length] + "\n");
			}
		}
		System.out.print(out);
	}