题提供二进制分解进位的思路。

得到多项式系数后，考虑对多项式进位。显然时不需要进位，考虑其他的的情况。一种比较直观的想法是，对进行二进制分解，二进制分解可以得到，显然，有。对于项，有。那么,实现进位。进位完成后考虑的变化，显然最后的系数与二进制第位有关。

需要注意的是，的正负性对带来的影响，毕竟负数多了一个,所以是。

特别的，对于是负数时，进位完成后可能变成,这显然不是我们想要的，其实很好解决，因为，所以此时需要再进一次位

最重要的是，由于不断进位，所以不能保证已经得到的系数数组是足够大的，特别是对来说，需要用扩容，保证数组不越界（因为这个导致了三小时还没发现问题，最后只能下班）。

对比官解，虽然提到解法很典，但是由于之前确实没接触过这种进位，所以看不懂题解，这种做法虽然麻烦，复杂度多了一些二进制枚举的常数，但是更容易推导与接受。两种做法最后的答案都一样，所以我想，这种做法与官解，本质上是相同的吧。

至于为什么要多项式算系数，我想当你发现读了半天题目还不知道怎么用原式推关于的多项式，但是用多项式却很好推进制表示，多项式相乘又能得到正确的相乘结果的时候，多项式乘法就呼之欲出了吧。

#include <bits/stdc++.h>
#define int long long

#include <complex>

const double PI = acos(-1.0);

void FFT(std::vector<std::complex<double>> &a, int ops) {
    int n = a.size();
    std::vector<int> rev(n);

    for (int i = 0; i < n; ++i) {
        rev[i] = (rev[i >> 1] >> 1);
        if (i & 1) {
            rev[i] |= (n >> 1);
        }
    }

    for (int i = 0; i < n; ++i) {
        if (i < rev[i]) {
            std::swap(a[i], a[rev[i]]);
        }
    }

    for (int i = 2; i <= n; i <<= 1) {
        int mid = i >> 1;
        std::complex<double> wn(cos(2 * PI * ops / i), sin(2 * PI * ops / i));
        for (int j = 0; j < n; j += i) {
            std::complex<double> w(1, 0);
            for (int k = 0; k < mid; ++k) {
                std::complex<double> x = a[j + k];
                std::complex<double> y = w * a[j + k + mid];
                a[j + k] = x + y;
                a[j + k + mid] = x - y;
                w *= wn;
            }
        }
    }

    if (ops == -1) {
        for (int i = 0; i < n; ++i) {
            a[i] /= n;
        }
    }
}

std::vector<int> mul(std::vector<int> &a, std::vector<int> &b) {
    int n = a.size(), m = b.size();
    int len = 1;
    while (len < n + m) {
        len <<= 1;
    }

    std::vector<std::complex<double>> A(len), B(len);
    for (int i = 0; i < n; i++) {
        A[i] = std::complex<double>(a[i], 0);
    }
    for (int i = 0; i < m; i++) {
        B[i] = std::complex<double>(b[i], 0);
    }

    FFT(A, 1);
    FFT(B, 1);

    std::vector<std::complex<double>> C(len);
    for (int i = 0; i < len; i++) {
        C[i] = A[i] * B[i];
    }

    FFT(C, -1);

    std::vector<int> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        c[i] = static_cast<int>(C[i].real() + 0.5);
        if (c[i] < 0) {
            c[i] = 0;
        }
    }

    return c;
}

void solve() {
    std::string s1, s2;
    std::cin >> s1 >> s2;

    int n = s1.size(), m = s2.size();
    std::vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        a[i] = (s1[n - i - 1] == '0' ? 0 : 1);
    }
    for (int i = 0; i < m; i++) {
        b[i] = (s2[m - i - 1] == '0' ? 0 : 1);
    }

    std::vector<int> c = mul(a, b);
    int len = c.size();

    auto work = [&](int i, int ops) -> void {
        int k, tmp = abs(c[i]);
        for (int j = 1; j <= 63; j++) {
            k = (tmp >> j) & 1;
            if (!k) {
                continue;
            }
            if (2 * j + i >= len) {
                len = 2 * j + i + 1;
                c.resize(len);
            }
            
            c[2 * j + i]+=ops*pow(-1,j);
           
        }
        k = (tmp >> 0) & 1;
        if (k) {
            c[i] = ops;
        } else {
            c[i] = 0;
        }
    };

    for (int i = 0; i < len; i++) {
        if (c[i] > 1) {
            work(i, 1);
        } else if (c[i] < 1) {
            work(i, -1);
            if (c[i] == -1) {
                if (i + 2 >= len) {
                    len = i + 3;
                    c.resize(len);
                }
                c[i + 2]++;
                c[i] = 1;
            }
        }
    }

    while (c.size() > 1 && c.back() == 0) {
        c.pop_back();
    }

    for (int i = c.size() - 1; i >= 0; i--) {
        std::cout << c[i];
    }
    std::cout << '\n';
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}