#include <bits/stdc++.h>
    #include <chrono>
    using namespace std;
    using namespace chrono;
    // "AJEET JAIN"----"JAI JINENDRA"  
    /* "णमो अरिहंताणं",
        "णमो सिद्धाणं",
        "णमो आयरियाणं",
        "णमो उवज्झायाणं",
        "णमो लोए सव्वसाहूणं",
        "",
        "एसो पंच नमोक्कारो, सव्व पावप्पणासणो",
        "मंगलाणं च सव्वेसिं, पडमं हवै मंगलं",   */
 
 
    // Aliases to op
    using ll = long long;
    using ull = unsigned long long;
    using ld = double;
    using vll = vector<ll>;
 
 
    // Constants
    constexpr ll INF = 4e18;
    constexpr ld EPS = 1e-9;
    constexpr ll MOD = 1e9 + 7;
 
 
 
    // Macros
    #define F first
    #define S second
    #define all(x) begin(x), end(x)
    #define allr(x) rbegin(x), rend(x)
    #define py cout<<"YES\n";
    #define pn cout<<"NO\n";
    #define forn(i,n) for(int i=0;i<n;i++)
    #define for1(i,n) for(int i=1;i<=n;i++)
 
    // #define insert push_back
    #define pb push_back
    #define MP make_pair
    #define endl '\n'
 
    /*
      remove substring or subarray ---> try to think about sliding w
    
    */                  
 
     /*
      
     Golden Rule
 
     1) problem is easy
     2) proofs is easy
     3) implementation is easy
     
     /*
         ROUGH --
                 
     */
 
    void AJNJ(){
       string s , t;
       cin >> s >> t;
       map<char , ll> mpt , mps;
       for(int i = 0 ; i < t.size() ; i++){
            mpt[t[i]]++;
       }
       forn(i , s.size()){
           mps[s[i]]++;
       }
       ll mini = INT_MAX;
       forn(i , t.size()){
          mini = min(mini , mps[t[i]]/mpt[t[i]]);
       }
 
       cout << mini << endl;
 
    }
 
 
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int T = 1;
        cin>>T;
        auto start1 = high_resolution_clock::now();
        while(T--){
            AJNJ();
        }
        auto stop1 = high_resolution_clock::now();
        auto duration = duration_cast<microseconds>(stop1 - start1);
        cerr << "Time: " << duration . count() / 1000 << " ms" << endl;
 
        return 0;
    }

ICAgICNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgogICAgI2luY2x1ZGUgPGNocm9ubz4KICAgIHVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAgICB1c2luZyBuYW1lc3BhY2UgY2hyb25vOwogICAgLy8gIkFKRUVUIEpBSU4iLS0tLSJKQUkgSklORU5EUkEiICAKICAgIC8qICLgpKPgpK7gpYsg4KSF4KSw4KS/4KS54KSC4KSk4KS+4KSj4KSCIiwKICAgICAgICAi4KSj4KSu4KWLIOCkuOCkv+CkpuCljeCkp+CkvuCko+CkgiIsCiAgICAgICAgIuCko+CkruCliyDgpIbgpK/gpLDgpL/gpK/gpL7gpKPgpIIiLAogICAgICAgICLgpKPgpK7gpYsg4KSJ4KS14KSc4KWN4KSd4KS+4KSv4KS+4KSj4KSCIiwKICAgICAgICAi4KSj4KSu4KWLIOCksuCli+CkjyDgpLjgpLXgpY3gpLXgpLjgpL7gpLngpYLgpKPgpIIiLAogICAgICAgICIiLAogICAgICAgICLgpI/gpLjgpYsg4KSq4KSC4KSaIOCkqOCkruCli+CkleCljeCkleCkvuCksOCliywg4KS44KS14KWN4KS1IOCkquCkvuCkteCkquCljeCkquCko+CkvuCkuOCko+CliyIsCiAgICAgICAgIuCkruCkguCkl+CksuCkvuCko+CkgiDgpJog4KS44KS14KWN4KS14KWH4KS44KS/4KSCLCDgpKrgpKHgpK7gpIIg4KS54KS14KWIIOCkruCkguCkl+CksuCkgiIsICAgKi8KICAgIAogICAgCiAgICAvLyBBbGlhc2VzIHRvIG9wCiAgICB1c2luZyBsbCA9IGxvbmcgbG9uZzsKICAgIHVzaW5nIHVsbCA9IHVuc2lnbmVkIGxvbmcgbG9uZzsKICAgIHVzaW5nIGxkID0gZG91YmxlOwogICAgdXNpbmcgdmxsID0gdmVjdG9yPGxsPjsKICAgIAogICAgCiAgICAvLyBDb25zdGFudHMKICAgIGNvbnN0ZXhwciBsbCBJTkYgPSA0ZTE4OwogICAgY29uc3RleHByIGxkIEVQUyA9IDFlLTk7CiAgICBjb25zdGV4cHIgbGwgTU9EID0gMWU5ICsgNzsKCgogICAgCiAgICAvLyBNYWNyb3MKICAgICNkZWZpbmUgRiBmaXJzdAogICAgI2RlZmluZSBTIHNlY29uZAogICAgI2RlZmluZSBhbGwoeCkgYmVnaW4oeCksIGVuZCh4KQogICAgI2RlZmluZSBhbGxyKHgpIHJiZWdpbih4KSwgcmVuZCh4KQogICAgI2RlZmluZSBweSBjb3V0PDwiWUVTXG4iOwogICAgI2RlZmluZSBwbiBjb3V0PDwiTk9cbiI7CiAgICAjZGVmaW5lIGZvcm4oaSxuKSBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgI2RlZmluZSBmb3IxKGksbikgZm9yKGludCBpPTE7aTw9bjtpKyspCgogICAgLy8gI2RlZmluZSBpbnNlcnQgcHVzaF9iYWNrCiAgICAjZGVmaW5lIHBiIHB1c2hfYmFjawogICAgI2RlZmluZSBNUCBtYWtlX3BhaXIKICAgICNkZWZpbmUgZW5kbCAnXG4nCgogICAgLyoKICAgICAgcmVtb3ZlIHN1YnN0cmluZyBvciBzdWJhcnJheSAtLS0+IHRyeSB0byB0aGluayBhYm91dCBzbGlkaW5nIHcKICAgIAogICAgKi8gICAgICAgICAgICAgICAgICAKCiAgICAgLyoKICAgICAgCiAgICAgR29sZGVuIFJ1bGUKCiAgICAgMSkgcHJvYmxlbSBpcyBlYXN5CiAgICAgMikgcHJvb2ZzIGlzIGVhc3kKICAgICAzKSBpbXBsZW1lbnRhdGlvbiBpcyBlYXN5CiAgICAgCiAgICAgLyoKICAgICAgICAgUk9VR0ggLS0KICAgICAgICAgICAgICAgICAKICAgICAqLwogICAgCiAgICB2b2lkIEFKTkooKXsKICAgICAgIHN0cmluZyBzICwgdDsKICAgICAgIGNpbiA+PiBzID4+IHQ7CiAgICAgICBtYXA8Y2hhciAsIGxsPiBtcHQgLCBtcHM7CiAgICAgICBmb3IoaW50IGkgPSAwIDsgaSA8IHQuc2l6ZSgpIDsgaSsrKXsKICAgICAgICAgICAgbXB0W3RbaV1dKys7CiAgICAgICB9CiAgICAgICBmb3JuKGkgLCBzLnNpemUoKSl7CiAgICAgICAgICAgbXBzW3NbaV1dKys7CiAgICAgICB9CiAgICAgICBsbCBtaW5pID0gSU5UX01BWDsKICAgICAgIGZvcm4oaSAsIHQuc2l6ZSgpKXsKICAgICAgICAgIG1pbmkgPSBtaW4obWluaSAsIG1wc1t0W2ldXS9tcHRbdFtpXV0pOwogICAgICAgfQoKICAgICAgIGNvdXQgPDwgbWluaSA8PCBlbmRsOwoKICAgIH0KCiAgICAKICAgIGludCBtYWluKCl7CiAgICAgICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICAgICAgY2luLnRpZSgwKTsKICAgICAgICBjb3V0LnRpZSgwKTsKICAgICAgICBpbnQgVCA9IDE7CiAgICAgICAgY2luPj5UOwogICAgICAgIGF1dG8gc3RhcnQxID0gaGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsKICAgICAgICB3aGlsZShULS0pewogICAgICAgICAgICBBSk5KKCk7CiAgICAgICAgfQogICAgICAgIGF1dG8gc3RvcDEgPSBoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpOwogICAgICAgIGF1dG8gZHVyYXRpb24gPSBkdXJhdGlvbl9jYXN0PG1pY3Jvc2Vjb25kcz4oc3RvcDEgLSBzdGFydDEpOwogICAgICAgIGNlcnIgPDwgIlRpbWU6ICIgPDwgZHVyYXRpb24gLiBjb3VudCgpIC8gMTAwMCA8PCAiIG1zIiA8PCBlbmRsOwogICAgCiAgICAgICAgcmV0dXJuIDA7CiAgICB9