Can anyone help me remove tle (time limit exceeded) from this?

Given integer n and array of string of length n. In each query (q of them) we are given l and r and we need to find LCP in this subsequence. Q and N <= 10^5. The sum of lengths of strings <= 10^5.

My code (CPP):

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

int lcp(string a, string b){
    int sol = 0;
    for (int i = 0; i < min(b.size(), a.size()); ++i){
        if (a[i] == b[i])
            ++sol;
        else
            break;
    }

    return sol;
}

int d[10000][10000];

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);  

    int t;
    cin >> t;

    for (int e = 0; e < t; ++e){
        int n;
        cin >> n;

        vs s(n);
        for (auto& i : s)
            cin >> i;

        int q;
        cin >> q;

        for (int i = 0; i < q; ++i){
            int l, r;
            cin >> l >> r;
            --l; --r;

            int sol = 0;
            for (int i = l; i < r; ++i){
                for (int j = i + 1; j <= r; ++j){
                    if (!d[i][j]){
                        d[i][j] = lcp(s[i], s[j]);
                        if (d[i][j] == 0)
                            d[i][j] = -1;
                    }
                    sol = max(sol, d[i][j]);
                }
            }

            cout << sol << '\n';
        }
    }
}