Problem E

Distinct Subsequences

Input: standard input<style=‘mso-bidi-font-weight:normal‘>

Output: standard output

A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally, given a sequenceX=x₁x₂…x_m, another sequence Z=z₁z₂…z_k is a subsequence of X if there exists a strictly increasing sequence <i₁, i₂, …, i_k> of indices of X such that for all j = 1, 2, …, k, we have x_ij=z_j. For example, Z=bcdb is a subsequence of X=abcbdab with corresponding index sequence < 2, 3, 5, 7 >.

In this problem your job is to write a program that counts the number of occurrences of Z in X as a subsequence such that each has a distinct index sequence.

Input

The first line of the input contains an integer N indicating the number of test cases to follow.

The first line of each test case contains a string X, composed entirely of lowercase alphabetic characters and having length no greater than 10,000. The second line contains another string Z having length no greater than 100 and also composed of only lowercase alphabetic characters. Be assured that neither Z nor any prefix or suffix of Z will have more than 10¹⁰⁰ distinct occurrences in X as a subsequence.

Output

For each test case in the input output the number of distinct occurrences of Z in X as a subsequence. Output for each input set must be on a separate line.

Sample Input

Sample Output

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <algorithm>using namespace std;const int MAXN = 110; //数组越大，时间复杂度越高啊，谨慎使用。 char X[10010], Y[110];struct bign{	int len, s[MAXN];	bign()	{		memset(s, 0, sizeof(s));		len = 1;	}	bign operator = (const char *num)	{		len = strlen(num);		for(int i = 0; i < len; i++) s[i] = num[len-i-1] - ‘0‘;		return *this; 	} 	bign operator = (const int num) 	{		char s[MAXN];		sprintf(s, "%d", num);		*this = s;		return *this;	}	bign (int num) { *this = num;}	bign (char *num) { *this = num;} 	bign operator + (const bign &b) 	{		bign c;		c.len = 0;		for(int i = 0, g = 0; g || i < max(len, b.len); i++)		{			int x = g;			if(i < len) x += s[i];			if(i < b.len) x += b.s[i];			c.s[c.len++] = x % 10;			g = x / 10;		}		return c;	}	bign operator - (const bign &b)	{		bign c;		c.len = 0;		for(int i = 0; i < max(len, b.len); i++)		{			c.s[i] += s[i]-b.s[i];			if(c.s[i] < 0)			{				c.s[i] += 10;				c.s[i+1]--;			}		}		while(c.s[len-1] == 0 && len > 1) len--;		c.len = len;		return c;	}	bign operator += (const bign &b)	{		*this = *this + b;		return *this;	}	string str() const	{		string res = "";		for(int i = 0; i < len; i++) res = char(s[i] + ‘0‘) + res;		if(res == "") res = "0";		return res;	}}d[110][10010];istream& operator >> (istream& in, bign &x){	string s;	in >> s;	x = s.c_str();	return in;}ostream& operator << (ostream& out, bign &x){	out << x.str();	return out;}void solve(){	scanf("%s%s", X+1, Y+1);	int lenX = strlen(X+1), lenY = strlen(Y+1);	for(int i = 0; i <= lenX; i++) d[0][i] = 1;	for(int i = 1; i <= lenY; i++)	{		for(int j = i; j <= lenX; j++)		{			d[i][j] = d[i][j-1];			if(Y[i] == X[j]) d[i][j] += d[i-1][j-1];		}	}	cout<<d[lenY][lenX]<<endl;}int main(){	int T;	scanf("%d", &T);	while(T--)	{		solve();	}	return 0;}