#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

// Function to convert a ternary string to a binary string
string ternaryToBinary(const string &s) {
    int ternaryValue = 0;
    for (char c : s) {
        ternaryValue = ternaryValue * 3 + (c - '0');
    }
    string binary = "";
    while (ternaryValue > 0) {
        binary = char((ternaryValue % 2) + '0') + binary;
        ternaryValue /= 2;
    }
    return binary.empty() ? "0" : binary;
}

// Function to perform the transformation and check if we can reach B from A
bool canTransform(string A, string B, vector<pair<int, int>> &operations) {
    queue<pair<string, int>> q;
    unordered_map<string, vector<pair<int, int>>> parent;
    q.push({A, 0});
    parent[A] = {};

    while (!q.empty()) {
        auto [current, steps] = q.front();
        q.pop();

        if (current == B) {
            // Reconstruct the path
            string temp = B;
            while (temp != A) {
                auto it = parent.find(temp);
                operations.insert(operations.begin(), it->second);
                temp = temp.substr(0, it->second.first - 1) + temp.substr(it->second.second);
            }
            return true;
        }

        if (steps >= 512) continue;

        for (int l = 1; l <= current.length(); ++l) {
            for (int r = l; r <= current.length(); ++r) {
                string sub = current.substr(l - 1, r - l + 1);
                string newSub = ternaryToBinary(sub);
                string newStr = current.substr(0, l - 1) + newSub + current.substr(r);

                if (newStr.length() > 128) continue;

                if (parent.find(newStr) == parent.end()) {
                    parent[newStr] = {l, r};
                    q.push({newStr, steps + 1});
                }
            }
        }
    }

    return false;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        string A, B;
        cin >> A >> B;

        vector<pair<int, int>> operations;
        if (canTransform(A, B, operations)) {
            cout << operations.size() << "\n";
            for (const auto &op : operations) {
                cout << op.first << " " << op.second << "\n";
            }
        } else {
            cout << "-1\n";
        }
    }

    return 0;
}

answer.code: In function ‘bool canTransform(std::string, std::string, std::vector<std::pair<int, int> >&)’:
answer.code:39:34: error: no matching function for call to ‘std::vector<std::pair<int, int> >::insert(std::vector<std::pair<int, int> >::iterator, std::vector<std::pair<int, int> >&)’
   39 |                 operations.insert(operations.begin(), it->second);
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/queue:63,
                 from answer.code:2:
/usr/include/c++/13/bits/stl_vector.h:1479:9: note: candidate: ‘template<class _InputIterator, class> std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, _InputIterator, _InputIterator) [with <template-parameter-2-2> = _InputIterator; _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >]’
 1479 |         insert(const_iterator __position, _InputIterator __first,
      |         ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:1479:9: note:   template argument deduction/substitution failed:
answer.code:39:34: note:   candidate expects 3 arguments, 2 provided
   39 |                 operations.insert(operations.begin(), it->second);
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:72:
/usr/include/c++/13/bits/vector.tcc:133:5: note: candidate: ‘std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; iterator = std::vector<std::pair<int, int> >::iterator; const_iterator = std::vector<std::pair<int, int> >::const_iterator; value_type = std::pair<int, int>]’
  133 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/vector.tcc:135:57: note:   no known conversion for argument 2 from ‘std::vector<std::pair<int, int> >’ to ‘const std::vector<std::pair<int, int> >::value_type&’ {aka ‘const std::pair<int, int>&’}
  135 |     insert(const_iterator __position, const value_type& __x)
      |                                       ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1390:7: note: candidate: ‘std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; iterator = std::vector<std::pair<int, int> >::iterator; const_iterator = std::vector<std::pair<int, int> >::const_iterator; value_type = std::pair<int, int>]’
 1390 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:1390:54: note:   no known conversion for argument 2 from ‘std::vector<std::pair<int, int> >’ to ‘std::vector<std::pair<int, int> >::value_type&&’ {aka ‘std::pair<int, int>&&’}
 1390 |       insert(const_iterator __position, value_type&& __x)
      |                                         ~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1408:7: note: candidate: ‘std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, std::initializer_list<_Tp>) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; iterator = std::vector<std::pair<int, int> >::iterator; const_iterator = std::vector<std::pair<int, int> >::const_iterator]’
 1408 |       insert(const_iterator __position, initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:1408:70: note:   no known conversion for argument 2 from ‘std::vector<std::pair<int, int> >’ to ‘std::initializer_list<std::pair<int, int> >’
 1408 |       insert(const_iterator __position, initializer_list<value_type> __l)
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1434:7: note: candidate: ‘std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, size_type, const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; iterator = std::vector<std::pair<int, int> >::iterator; const_iterator = std::vector<std::pair<int, int> >::const_iterator; size_type = long unsigned int; value_type = std::pair<int, int>]’
 1434 |       insert(const_iterator __position, size_type __n, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:1434:7: note:   candidate expects 3 arguments, 2 provided
answer.code:40:50: error: ‘class std::vector<std::pair<int, int> >’ has no member named ‘first’
   40 |                 temp = temp.substr(0, it->second.first - 1) + temp.substr(it->second.second);
      |                                                  ^~~~~
answer.code:40:86: error: ‘class std::vector<std::pair<int, int> >’ has no member named ‘second’
   40 |                 temp = temp.substr(0, it->second.first - 1) + temp.substr(it->second.second);
      ...