ABC 430

ll modpow(ll x, ll n, ll mod) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1)
            ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

struct RollingHash {
    vll data;
    const ll p = 1000000009;
    const ll mod = 1000000021;

    RollingHash(vll& v) {
        int n = v.size();
        data.resize(n + 1);
        rep(i, n) {
            data[i + 1] = (data[i] * p % mod) + v[i];
            data[i + 1] %= mod;
        }
    };

    // [l,r) の範囲の hash 値
    ll sub(ll l, ll r) {
        ll m = r - l;
        ll x = data[r] - data[l] * modpow(p, m, mod) % mod;
        x += mod;
        x %= mod;
        return x;
    }
};

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        string A, B;
        cin >> A >> B;

        vll va, vb;
        int N = A.size();
        rep(i, N) {
            va.push_back(A[i] == '1');
            vb.push_back(B[i] == '1');
        }

        ll ans = INF;
        RollingHash ha(va), hb(vb);
        ll targetHash = hb.sub(0, N);
        rep(i, N) {
            ll newHash = ha.sub(i, N) * modpow(ha.p, i, ha.mod) % ha.mod + ha.sub(0, i);
            newHash %= ha.mod;
            if (newHash == targetHash) chmin(ans, i);
        }

        if (ans == INF) ans = -1;
        cout << ans << '\n';
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        string A, B;
        cin >> A >> B;

        string S = B + A + A;

        vint z = z_algorithm(S);

        int n = A.size();
        rep(i, n) {
            if (z[n + i] >= n) {
                cout << i << '\n';
                return;
            }
        }
        cout << -1 << '\n';
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}