# nhphuc's templates

1. Simple start code:

/**
 *    Author: Nguyen Huu Phuc
 *    - Fan Dang Doan Duc Trung 20 nam -
**/ 

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

#define int long long
#define pb  push_back
#define f   first
#define s   second

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
        
}
// uoc co cm

2. Multitest start code:

/**
 *   Author: Nguyen Huu Phuc
 *   - Fan Dang Doan Duc Trung 20 nam -
**/

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

#define int long long
#define pb  push_back
#define f   first
#define s   second

void solve(){

}

signed main(){
    if (fopen("TEST.inp", "r")){
        freopen("TEST.inp", "r", stdin);
        freopen("TEST.out", "w", stdout);
    }
    ios::sync_with_stdio(0); cin.tie(0);
    int tt; cin >> tt; while (tt--) solve();
}
// uoc co cm

3. Hash template

// hash template
const int listmod[] = {
    81576343,
    43179113,
    41328541,
    85003693,
    19498169,
    33145051,
    64018973,
    34085083,
    63017569,
    29469859,
    42387601,
    58168027,
    49709669,
    36439723,
    20622821,
    75275591,
    96992843,
    73858823,
    34106713,
    57137147,
    63717893,
    64778221,
    68839153,
    12584711,
    62176853,
    48996947,
    67124723,
    61760467,
    83064101,
    45952063
};

const int listbase[] = {
    431,
    593,
    443,
    607,
    379,
    401,
    937,
    571,
    857,
    727
};

const int N = 2e5 + 1;
const int L = 2;       // can up to 6

mt19937_64 rng(static_cast<int>(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count()));

int rand(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

struct hash_st {
    int p[N][L], h[N][L], rp[N][L], rh[N][L];
    int mod[L], base = -1;
    void init_l (int n, string s){
        if (base == -1){
            base = listbase[rand(0, 9)];
            set<int> st;
            while (st.size() < L) st.insert(listmod[rand(0, 29)]);
            int id = 0;
            for (auto v : st) mod[id] = v, ++id;
        }
        for (int i = 0; i < L; ++i) p[0][i] = 1, h[0][i] = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j < L; ++j)
                p[i][j] = (p[i - 1][j] * base) % mod[j];
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j < L; ++j)
                h[i][j] = (h[i - 1][j] * base + (int)(s[i - 1]) + 1) % mod[j];
        cerr << "base use in init_l:\n" << base << "\n";
        cerr << "mod use in init_l:\n";
        for (int i = 0; i < L; ++i) cerr << mod[i] << "\n";
    }
    void init_r (int n, string s){
        if (base == -1){
            base = listbase[rand(0, 9)];
            set<int> st;
            while (st.size() < L) st.insert(listmod[rand(0, 29)]);
            int id = 0;
            for (auto v : st) mod[id] = v, ++id;
        }
        for (int i = 0; i < L; ++i) rp[n + 1][i] = 1, rh[n + 1][i] = 0;
        for (int i = n; i >= 1; --i)
            for (int j = 0; j < L; ++j)
                rp[i][j] = (rp[i + 1][j] * base) % mod[j];
        for (int i = n; i >= 1; --i)
            for (int j = 0; j < L; ++j)
                rh[i][j] = (rh[i + 1][j] * base + (int)(s[i - 1]) + 1) % mod[j];
        cerr << "base use in init_r:\n" << base << "\n";
        cerr << "mod use in init_r:\n";
        for (int i = 0; i < L; ++i) cerr << mod[i] << "\n";
    }
    vector<int> get_l (int l, int r){
        vector<int> ans(L);
        for (int i = 0; i < L; ++i)
            ans[i] = (h[r][i] - h[l - 1][i] * p[r - l + 1][i] + mod[i] * mod[i]) % mod[i];
        return ans;
    }
    vector<int> get_r (int l, int r){
        vector<int> ans(L);
        for (int i = 0; i < L; ++i)
            ans[i] = (rh[l][i] - rh[r + 1][i] * p[r - l + 1][i] + mod[i] * mod[i]) % mod[i];
        return ans;
    }
    bool palindrome (int l, int r){
        return get_l(l, r) == get_r(l, r);
    }
};
// end of hash template

4. Z-algo template

// z-algo template
struct zfunc {
    vector<int> z;
    void init (string s){
        int n = s.size(); z.resize(n);
        int l = 0, r = 0; z[0] = n;
        for (int i = 1; i < n; ++i)
            if (i > r){
                l = r = i;
                while (r < n && s[r] == s[r - l]) ++r;
                z[i] = r - i; --r;
            } else {
                int k = i - l;
                if (z[k] < r - i + 1) z[i] = z[k];
                else {
                    l = i;
                    while (r < n && s[r] == s[r - l]) ++r;
                    z[i] = r - l; --r;
                }
            }
        return;
    }
    int get (int pref, int n){
        int cnt = 0;
        for (int i = 0; (i + pref - 1) < n; )
            if (z[i] >= pref) ++cnt, i += pref;
            else i += 1;
        return cnt;
    }
};
// end of z-algo template