KMP

//manish kumar patel
#include<bits/stdc++.h>
using namespace std;



#define ll long long
#define ld long double
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define err() cout<<"--------------------------"<<endl; 
#define errA(A) for(auto i:A)   cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl



#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl
#define pb push_back
#define all(A)  A.begin(),A.end()
#define allr(A)    A.rbegin(),A.rend()
#define ft first
#define sd second

#define pii pair<int,int>
#define pll pair<ll,ll>
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
 
#define endl "\n"

V KMP_pre(string s)
{
    int l=s.length();
    V v(l,0);
    int i=0,j=1;
    // i is length of the matched prefix uptil there
    while(j<l)
    {
        if(s[i]==s[j])
        {
            v[j]=i+1;
            i+=1;
            j+=1;
        }
        else
        {
            if(i!=0)
            {
                i=v[i-1];
            }
            else
            {
                v[j]=0;
                ++j;
            }
        }
    }
    return v;
}

V KMP_search(string s,string pat,V v)
{
    int l1=s.length();
    int l2=pat.length();
    V vv;
    int i=0,j=0;
    while(i<l1)
    {
        if(s[i]==pat[j])
        {
            ++i;
            ++j;
        }
        if(j==l2)
        {
            vv.pb(i-l2);
            j=v[j-1];
        }
        else if(i<l1 && s[i]!=pat[j])
        {
            if(j!=0)
                j=v[j-1];
            else
                i+=1;

        }
    }
    return vv;
}

int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
        #ifndef ONLINE_JUDGE
         clock_t tStart = clock();
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        #endif
        int t;
        cin>>t;
        // t=1;
           
        while(t--)
        {
            string s,pat;
            cin>>s>>pat;
            V v=KMP_pre(pat);
            V vv=KMP_search(s,pat,v);
            errA(v);
            errA(vv);


        }
        #ifndef ONLINE_JUDGE
            printf("\nRun Time -> %.10fs\n", (double)(clock()-tStart) / CLOCKS_PER_SEC);
            #endif
}