AddChar

/// O(N * 2 sigma) / test
#include <bits/stdc++.h>
#define N 10005
using namespace std;

int T, d[54];
bool f[54];
char A[N], B[N];

int cod(char c)
{
    if(c >= 'A' && c <= 'Z') return c - 'A';
                        else return c - 'a' + 26;
}
void solve()
{
    memset(d, 0, sizeof(d));
    memset(f, 0, sizeof(f));

    scanf("%s\n", A + 1);
    scanf("%s\n", B + 1);

    int n = strlen(A + 1);
    int m = strlen(B + 1);

    for(int i = 1; i <= m; ++i)
        f[cod(B[i])] = 1;

    if(A[1] == '*'){
        for(int i = 0; i < 52; ++i)
            d[i] = f[i];
    } else d[cod(A[1])] = 1;

    for(int i = 1; i < 52; ++i)
        d[i] = max(d[i - 1], d[i]);

    for(int i = 2; i <= n; ++i){

        if(A[i]=='*'){
            if(f[0]) d[0] = max(d[0], 1);
            for(int i = 51; i >= 1; --i){
                if(f[i])
                    d[i] = max(d[i], d[i - 1] + 1);
            }
        } else{
            int c = cod(A[i]);
            if(c==0) d[0] = max(d[0], 1);
                else d[c] = max(d[c], d[c - 1] + 1);
        }
        for(int i = 1; i < 52; ++i)
            d[i] = max(d[i], d[i - 1]);
    }

    printf("%d\n", d[51]);
}

int main()
{
    freopen("addchar.in", "r", stdin);
    freopen("addchar.out","w", stdout);

    scanf("%d\n", &T);
    while (T--)
        solve();
    return 0;
}