Morgan and a String

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

pair<int, bool> helper(string& a, string& b, int i, int j) {
    int ap = 0, ext = 0;
    while(i + ap < a.length() and j + ap < b.length() and a[i] == a[i+ap] and a[i+ap] == b[j+ap]) ap++, ext++;
    while(i + ext < a.length() and j + ext < b.length() and a[i] >= a[i+ext] and a[i+ext] == b[j+ext]) ext++;
    if(i + ext < a.length() and j + ext < b.length()) {
        return {ap, a[i+ext] < b[j+ext]};
    } else {
        return {ap, i + ext != a.length()};
    }
}

string solve(string& a, string& b) {
    string res = "";
    int i = 0, j = 0;
    while(i < a.length() and j < b.length()) {
        if(a[i] == b[j]) {
            auto [ap, pi] = helper(a,b,i,j);
            if(pi) {
                res += string(ap, a[i]);
                i += ap;
            } else {
                res += string(ap, b[j]);
                j += ap;
            }
        }
        else if(a[i] < b[j]) res += a[i++];
        else res += b[j++];
    }
    
    if(i < a.length()) res += a.substr(i);
    if(j < b.length()) res += b.substr(j);
    return res;
}

int main() {
    int tc;
    cin>>tc;
    while(tc--) {
        string a, b;
        cin>>a>>b;
        cout<<solve(a,b)<<endl;
    }
    return 0;
}