UVa 10069 - Distinct Subsequences

// UVa 10069 - Distinct Subsequences
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int cases = scan.nextInt();
		scan.nextLine();
		for (; cases > 0; cases--) {
			String a = scan.nextLine();
			String b = scan.nextLine();
			BigInteger[][] T = new BigInteger[10000][100];
			T[0][0] = a.charAt(0) == b.charAt(0) ? BigInteger.ONE : BigInteger.ZERO;
			for (int i = 1; i < a.length(); i++) {
				T[i][0] = T[i - 1][0];
				if (a.charAt(i) == b.charAt(0))
					T[i][0] = T[i][0].add(BigInteger.ONE);
			}
			for (int j = 1; j < b.length(); j++) {
				T[j - 1][j] = BigInteger.ZERO;
				for (int i = j; i < a.length(); i++) {
					T[i][j] = T[i - 1][j];
					if (a.charAt(i) == b.charAt(j))
						T[i][j] = T[i][j].add(T[i - 1][j - 1]);
				}
			}
			System.out.println(T[a.length() - 1][b.length() - 1]);
		}

	}

}