#include<cstdio>
#include<cassert>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
using namespace std;
typedef long long ll;
typedef double db;
const db pi=acos(-1);
void gn(int &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
void gn(ll &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
const int mo=1000000007;
int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

char x[1005],y[1005];
int n,m;
int f[1005][1005],g[1005][1005];
int main()
{
    int tes;
    scanf("%d",&tes);
    while(tes--){
        scanf("%s",x+1);
        scanf("%s",y+1);
        n=strlen(x+1);
        m=strlen(y+1);
        for (int i=0;i<=n;i++)g[i][0]=1;
        for (int i=0;i<=m;i++)g[0][i]=1;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++){
                if(x[i]==y[j]){
                    f[i][j]=f[i-1][j-1]+1;
                    g[i][j]=g[i-1][j-1];
                    if(f[i-1][j]==f[i][j])g[i][j]=(g[i][j]+g[i-1][j])%mo;
                }else{
                    f[i][j]=max(f[i-1][j],f[i][j-1]);
                    if(f[i][j]==0)g[i][j]=1;
                    else{
                        if(f[i-1][j]!=f[i][j-1]){
                            if(f[i][j]==f[i-1][j])g[i][j]=g[i-1][j];
                            else if(f[i][j]==f[i][j-1])g[i][j]=g[i][j-1];
                        }else{
                            if(f[i-1][j-1]==f[i][j])
                                g[i][j]=((g[i-1][j]+g[i][j-1]-g[i-1][j-1])%mo+mo)%mo;
                            else
                                g[i][j]=((g[i-1][j]+g[i][j-1])%mo+mo)%mo;
                        }
                    }
                }
            }
        printf("%d\n",g[n][m]);
    }
    return 0;
}