This problem can be solved with the idea of canonical form.

For a string \(S\) consisting of (, x, and ), define its canonical form \(f(S)\) as:

• the string resulting form repeatedly replacing any substring (xx) of \(S\) into xx as many times as possible.

Then \(f(S)\) is uniquely determined regardless of operations.

(Proof) (It may be a bit difficult. You may skip this.)
We prove it by induction. We assume the uniqueness of the canonical form of a string of length \((k-1)\) or less, and will prove the uniqueness of the canonical form a string of length \(k\).
Suppose that there are \(m\) occurrences of (xx) in a length-\(k\) string \(S\). Obviously, (xx) are all disjoint. We consider cases where \(m=0, 1\), and others separately.

• If \(m=0\): the canonical form of \(S\) is \(S\) itself.
• If \(m=1\): the canonical form of \(S\) is obtained by replacing the unique occurrence of (xx) with xx in \(S\). After the replacement, \(S\) has a length \((k-2)\), whose canonical form is guaranteed unique by assumption.
• If \(m \geq 2\): Take two occurrences of (xx) in \(S\), and call them \(a\) and \(b\). Note that replacing \(a\) with xx does not affect to the existence of \(b\) (and vice versa).
  Let \(S_a\) be the string obtained by replacing \(a\) with xx in \(S\). Since \(S_a\) has a length \(k-2\), by the inductive assumption the canonical form of \(S_a\) equals the canonical form of the string obtained by replacing \(b\) with xx in \(S_a\).
  Meanwhile, let \(S_b\) be the string obtained by replacing \(b\) with xx in \(S\). Since \(S_b\) has a length \(k-2\), by the inductive assumption the canonical form of \(S_b\) equals the canonical form of the string obtained by replacing \(a\) with xx in \(S_b\).
  Here, the string obtained by replacing \(b\) with xx in \(S_a\) coincides with the string obtained by replacing \(a\) with xx in \(S_b\). Therefore, the canonical forms of \(S_a\) and \(S_b\) are equal. Since this discussion can be applied to any choice of \(a\) and \(b\), it turns out that replacing any occurrence of (xx) in \(S\) with xx first ends up in an unique canonical form.

This concludes the proof. (End of proof)

We have shown the uniqueness of the canonical form a string \(S\). We further has the following fact:

• The following are equivalent:
  • (1) Once can repeatedly perform the operations in the problem statement against string \(A\) to make \(A\) equal to \(B\).
  • (2) \(f(A) = f(B)\).

(Proof) (It may be a bit difficult. You may skip this.)

(2) \(\to\) (1): Take any operation sequence \(v\) that transforms \(A\) into \(f(A)\), and any operation sequence \(w\) that transforms \(B\) into \(f(B)\).
By applying operation according to the operation sequence \(v\) on \(A\), it turns to \(f(A)\). Then, by applying the reverse actions according to the operation sequence \(w\), that is, replacing xx with (xx), we can transform \(f(A) = f(B)\) into \(B\).

(1) \(\to\) (2): For any string \(S\), let

• \(S'\) be the string obtained by replacing an occurrence of xx as a substring of \(S\) with (xx), and
• \(S''\) be the string obtained by replacing an occurrence of (xx) as a substring of \(S\) with xx.

By the uniqueness of a canonical form, if \(S'\) and \(S''\) exist, then \(f(S)=f(S')\) and \(f(S)=f(S'')\) hold. This implies that a canonical form is invariant by an operation, which means if (1) holds, \(f(A) = f(B)\) must hold.

(End of proof)

By these facts, it turns out that the problem can be solved by finding the canonical form \(f(A)\) of a string \(A\).

\(f(A)\) can be computed using a stack. Specifically, the following algorithm yields the canonical form \(f(A)\):

• Prepare an empty string \(C\).
• For \(i=1,2,\dots,|A|\) in order, perform the following:
  • Append \(A_i\) to the end of \(C\).
  • If the last four characters of \(C\) are (xx), replace it with xx.
• The resulting string \(C\) is \(f(A)\).

This algorithm runs in \(\mathrm{O}(|A|)\) time. Therefore, the problem can be solved in a total of \(\mathrm{O}(|A|+|B|)\) time, which is fast enough.

• Sample code (C++)

#include <iostream>
#include <string>
using namespace std;

string canonical_form(const string& S) {
  string T;
  for (auto& c : S) {
    T.push_back(c);
    if ((int)T.size() >= 4 and T.substr(T.size() - 4, 4) == "(xx)") {
      T.erase(end(T) - 4, end(T));
      T += "xx";
    }
  }
  return T;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) {
    string A, B;
    cin >> A >> B;
    cout << (canonical_form(A) == canonical_form(B) ? "Yes" : "No") << "\n";
  }
}