Problem: This is the easy version of the problem. The difference between the versions is the constraint on n and the required number of operations. You can make hacks only if all versions of the problem are solved.

There are two binary strings a and b of length n (a binary string is a string consisting of symbols 0 and 1). In an operation, you select a prefix of a, and simultaneously invert the bits in the prefix (0 changes to 1 and 1 changes to 0) and reverse the order of the bits in the prefix.

For example, if a=001011 and you select the prefix of length 3, it becomes 011011. Then if you select the entire string, it becomes 001001.

Your task is to transform the string a into b in at most 3n operations. It can be proved that it is always possible.

Input

The first line contains a single integer t (1≤ t≤ 1000) — the number of test cases. Next 3t lines contain descriptions of test cases.

The first line of each test case contains a single integer n (1≤ n≤ 1000) — the length of the binary strings.

The next two lines contain two binary strings a and b of length n.

It is guaranteed that the sum of n across all test cases does not exceed 1000.

Output

For each test case, output an integer k (0≤ k≤ 3n), followed by k integers p_1,…,p_k (1≤ p_i≤ n). Here k is the number of operations you use and p_i is the length of the prefix you flip in the i-th operation.

Example

Input


5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1


Output


3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1

Note

In the first test case, we have 01→ 11→ 00→ 10.

In the second test case, we have 01011→ 00101→ 11101→ 01000→ 10100→ 00100→ 11100.

In the third test case, the strings are already the same. Another solution is to flip the prefix of length 2, which will leave a unchanged.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("-Ofast")
std::ifstream ___in("input.in");
using namespace std;
using ll = long long;
static const bool tc = 1;
static const ll mod = LLONG_MAX - 24;
template <class T>
class segmentTree {
 private:
  int _n, _cfg;
  const T ST_MAX_VAL;
  bool _stl;
  vector<T> _v[5];
  vector<typename vector<T>::iterator> _to;
  typename vector<T>::iterator _vstart;
  T *_start;
  void _lazySumUpdate(const int _node, const int _nowL, const int _nowR,
                      const T _val) {
    bool _pending = (_val == 0);
    if (_cfg & 1) _v[0][_node] += (_pending ? _v[3][_node] : _val);
    if (_cfg & 2) _v[1][_node] += (_pending ? _v[3][_node] : _val);
    if (_cfg & 4)
      _v[2][_node] += (_nowR - _nowL + 1) * (_pending ? _v[3][_node] : _val);
    if (_nowL != _nowR) {
      _v[3][2 * _node] += (_pending ? _v[3][_node] : _val);
      _v[3][2 * _node + 1] += (_pending ? _v[3][_node] : _val);
    }
    _v[3][_node] = 0;
  }
  void _updateLazySums(const int _node, const int _nowL, const int _nowR,
                       const int _tL, const int _tR) {
    if (_v[3][_node] != 0) _lazySumUpdate(_node, _nowL, _nowR, 0);
    if (_nowL > _tR || _nowR < _tL || _nowL == _nowR ||
        (_tL <= _nowL && _nowR <= _tR))
      return;
    int _m = (_nowL + _nowR) / 2;
    _updateLazySums(2 * _node, _nowL, _m, _tL, _tR);
    _updateLazySums(2 * _node + 1, _m + 1, _nowR, _tL, _tR);
    if (_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
    if (_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
    if (_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
  }
  void _lazyAssignUpdate(const int _node, const int _nowL, const int _nowR,
                         const T _val) {
    bool _pending = (_val == ST_MAX_VAL);
    if (_cfg & 1) _v[0][_node] = (_pending ? _v[4][_node] : _val);
    if (_cfg & 2) _v[1][_node] = (_pending ? _v[4][_node] : _val);
    if (_cfg & 4)
      _v[2][_node] = (_nowR - _nowL + 1) * (_pending ? _v[4][_node] : _val);
    if (_nowL != _nowR) {
      _v[4][2 * _node] = (_pending ? _v[4][_node] : _val);
      _v[4][2 * _node + 1] = (_pending ? _v[4][_node] : _val);
    }
    _v[4][_node] = ST_MAX_VAL;
  }
  void _updateLazyAssigns(const int _node, const int _nowL, const int _nowR,
                          const int _tL, const int _tR) {
    if (_v[4][_node] != ST_MAX_VAL)
      _lazyAssignUpdate(_node, _nowL, _nowR, ST_MAX_VAL);
    if (_nowL > _tR || _nowR < _tL || _nowL == _nowR ||
        (_tL <= _nowL && _nowR <= _tR))
      return;
    int _m = (_nowL + _nowR) / 2;
    _updateLazyAssigns(2 * _node, _nowL, _m, _tL, _tR);
    _updateLazyAssigns(2 * _node + 1, _m + 1, _nowR, _tL, _tR);
    if (_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
    if (_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
    if (_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
  }
  void _setUp(const int _node, const int _l, const int _r) {
    if (_l == _r) {
      for (int i = 0; i < 3; ++i)
        if ((_cfg >> i) & 1) {
          _to[_l] = (_v[i].begin() + _node);
          break;
        }
      for (int i = 0; i < 3; ++i)
        if ((_cfg >> i) & 1) {
          if (_stl)
            _v[i][_node] = *(_vstart + _l - 1);
          else
            _v[i][_node] = *(_start + _l - 1);
        }
      return;
    }
    int _m = (_l + _r) / 2;
    _setUp(2 * _node, _l, _m);
    _setUp(2 * _node + 1, _m + 1, _r);
    if (_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
    if (_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
    if (_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
  }
  void _addToInterval(const int _node, const int _nowL, const int _nowR,
                      const int _tL, const int _tR, const T _val) {
    if (_v[3][_node] != 0) _lazySumUpdate(_node, _nowL, _nowR, 0);
    if (_nowL > _tR || _nowR < _tL) return;
    if (_tL <= _nowL && _nowR <= _tR) {
      _lazySumUpdate(_node, _nowL, _nowR, _val);
      return;
    }
    int _m = (_nowL + _nowR) / 2;
    _addToInterval(2 * _node, _nowL, _m, _tL, _tR, _val);
    _addToInterval(2 * _node + 1, _m + 1, _nowR, _tL, _tR, _val);
    if (_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
    if (_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
    if (_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
  }
  void _assignToInterval(const int _node, const int _nowL, const int _nowR,
                         const int _tL, const int _tR, const T _val) {
    if (_v[4][_node] != ST_MAX_VAL)
      _lazyAssignUpdate(_node, _nowL, _nowR, ST_MAX_VAL);
    if (_nowL > _tR || _nowR < _tL) return;
    if (_tL <= _nowL && _nowR <= _tR) {
      _lazyAssignUpdate(_node, _nowL, _nowR, _val);
      return;
    }
    int _m = (_nowL + _nowR) / 2;
    _assignToInterval(2 * _node, _nowL, _m, _tL, _tR, _val);
    _assignToInterval(2 * _node + 1, _m + 1, _nowR, _tL, _tR, _val);
    if (_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
    if (_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
    if (_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
  }
  T _intervalSum(const int _node, const int _nowL, const int _nowR,
                 const int _tL, const int _tR) {
    if (_tL <= _nowL && _nowR <= _tR) return _v[2][_node];
    int _m = (_nowL + _nowR) / 2;
    T _s = 0;
    if (_tL <= _m) _s += _intervalSum(2 * _node, _nowL, _m, _tL, _tR);
    if (_tR > _m) _s += _intervalSum(2 * _node + 1, _m + 1, _nowR, _tL, _tR);
    return _s;
  }
  T _minRange(const int _node, const int _nowL, const int _nowR, const int _tL,
              const int _tR) {
    if (_tL <= _nowL && _nowR <= _tR) return _v[0][_node];
    int _m = (_nowL + _nowR) / 2;
    T _min = ST_MAX_VAL;
    if (_tL <= _m) _min = min(_min, _minRange(2 * _node, _nowL, _m, _tL, _tR));
    if (_tR > _m)
      _min = min(_min, _minRange(2 * _node + 1, _m + 1, _nowR, _tL, _tR));
    return _min;
  }
  T _maxRange(const int _node, const int _nowL, const int _nowR, const int _tL,
              const int _tR) {
    if (_tL <= _nowL && _nowR <= _tR) return _v[1][_node];
    int _m = (_nowL + _nowR) / 2;
    T _max = -ST_MAX_VAL < 0ll ? -ST_MAX_VAL : 0;
    if (_tL <= _m) _max = max(_max, _maxRange(2 * _node, _nowL, _m, _tL, _tR));
    if (_tR > _m)
      _max = max(_max, _maxRange(2 * _node + 1, _m + 1, _nowR, _tL, _tR));
    return _max;
  }
  void _resize(const int _new) {
    _n = _new;
    for (int i = 0; i < 5; ++i)
      if (_cfg & (1 << i))
        _v[i].resize(4 * _new + 1);
      else
        _v[i].clear();
    _to.clear();
    _to.resize(_new + 1);
  }
  void _setPos(const int _node, const int _l, const int _r, const int _p,
               const int _val) {
    if (_l == _r) {
      for (int i = 0; i < 3; ++i)
        if ((_cfg >> i) & 1) _v[i][_node] = _val;
      return;
    }
    int _m = (_l + _r) / 2;
    if (_p <= _m)
      _setPos(2 * _node, _l, _m, _p, _val);
    else
      _setPos(2 * _node + 1, _m + 1, _r, _p, _val);
    if (_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
    if (_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
    if (_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
  }
  void _addOnPos(const int _node, const int _l, const int _r, const int _p,
                 const int _val) {
    if (_l == _r) {
      for (int i = 0; i < 3; ++i)
        if ((_cfg >> i) & 1) _v[i][_node] += _val;
      return;
    }
    int _m = (_l + _r) / 2;
    if (_p <= _m)
      _addOnPos(2 * _node, _l, _m, _p, _val);
    else
      _addOnPos(2 * _node + 1, _m + 1, _r, _p, _val);
    if (_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
    if (_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
    if (_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
  }
  T _on(const int _p) { return *_to[_p]; }
  void _upd(const int _node, const int _nowL, const int _nowR) {
    if ((_cfg & 8) && _v[3][_node] != 0) _lazySumUpdate(_node, _nowL, _nowR, 0);
    if ((_cfg & 16) && _v[4][_node] != ST_MAX_VAL)
      _lazyAssignUpdate(_node, _nowL, _nowR, ST_MAX_VAL);
    if (_nowL == _nowR) return;
    int _m = (_nowL + _nowR) / 2;
    _upd(2 * _node, _nowL, _m);
    _upd(2 * _node + 1, _m + 1, _nowR);
    if (_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
    if (_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
    if (_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
  }

 public:
  segmentTree()
      : _n(0),
        _cfg(0),
        ST_MAX_VAL(-1ll + (1ll << (sizeof(T) * 8 -
                                   (T)(((T)0 >= 0 && (T)~0 >= 0) ^ 1)))) {}
  void setUp(T *_a, T *_b, const int _newcfg) {
    _cfg = _newcfg;
    _resize(_b - _a + 1);
    _start = _a;
    _stl = 0;
    fill(_v[0].begin(), _v[0].end(), ST_MAX_VAL);
    fill(_v[4].begin(), _v[4].end(), ST_MAX_VAL);
    for (int i = 1; i < 4; ++i) fill(_v[i].begin(), _v[i].end(), 0);
    _setUp(1, 1, _n);
  }
  void setUp(typename vector<T>::iterator _a, typename vector<T>::iterator _b,
             const int _newcfg) {
    _cfg = _newcfg;
    _resize(_b - _a + 1);
    _vstart = _a;
    _stl = 1;
    fill(_v[0].begin(), _v[0].end(), ST_MAX_VAL);
    fill(_v[4].begin(), _v[4].end(), ST_MAX_VAL);
    for (int i = 1; i < 4; ++i) fill(_v[i].begin(), _v[i].end(), 0);
    _setUp(1, 1, _n);
  }
  void setUp(const int _sz, const int _newcfg) {
    _cfg = _newcfg;
    _resize(_sz);
    fill(_v[0].begin(), _v[0].end(), ST_MAX_VAL);
    fill(_v[4].begin(), _v[4].end(), ST_MAX_VAL);
    for (int i = 1; i < 4; ++i) fill(_v[i].begin(), _v[i].end(), 0);
  }
  void addToInterval(const int _l, const int _r, const int _val) {
    if ((_cfg & 8) == 0) exit(-1);
    if (_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
    _addToInterval(1, 1, _n, _l, _r, _val);
  }
  void assignToInterval(const int _l, const int _r, const int _val) {
    if ((_cfg & 16) == 0) exit(-1);
    if (_cfg & 8) _updateLazySums(1, 1, _n, _l, _r);
    if (_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
    _assignToInterval(1, 1, _n, _l, _r, _val);
  }
  void addOnPos(const int _p, const int _val) {
    if (_cfg & 8) _updateLazySums(1, 1, _n, _p, _p);
    if (_cfg & 16) _updateLazyAssigns(1, 1, _n, _p, _p);
    _addOnPos(1, 1, _n, _p, _val);
  }
  void setPos(const int _p, const int _val) {
    if (_cfg & 8) _updateLazySums(1, 1, _n, _p, _p);
    if (_cfg & 16) _updateLazyAssigns(1, 1, _n, _p, _p);
    _setPos(1, 1, _n, _p, _val);
  }
  T intervalSum(const int _l, const int _r) {
    if ((_cfg & 4) == 0) exit(-1);
    if (_cfg & 8) _updateLazySums(1, 1, _n, _l, _r);
    if (_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
    return _intervalSum(1, 1, _n, _l, _r);
  }
  T minRange(const int _l, const int _r) {
    if ((_cfg & 1) == 0) exit(-1);
    if (_cfg & 8) _updateLazySums(1, 1, _n, _l, _r);
    if (_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
    return _minRange(1, 1, _n, _l, _r);
  }
  T maxRange(const int _l, const int _r) {
    if ((_cfg & 2) == 0) exit(-1);
    if (_cfg & 8) _updateLazySums(1, 1, _n, _l, _r);
    if (_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
    return _maxRange(1, 1, _n, _l, _r);
  }
  void print() {
    if (_cfg & 8) _updateLazySums(1, 1, _n, 1, _n);
    if (_cfg & 16) _updateLazyAssigns(1, 1, _n, 1, _n);
    _upd(1, 1, _n);
    for (int i = 1; i <= _n; ++i) cout << _on(i) << " ";
    cout << "\n";
  }
  vector<T> toVector() {
    if (_cfg & 8) _updateLazySums(1, 1, _n, 1, _n);
    if (_cfg & 16) _updateLazyAssigns(1, 1, _n, 1, _n);
    _upd(1, 1, _n);
    vector<T> _vv(_n + 1);
    for (int i = 1; i <= _n; ++i) _vv[i] = _on(i);
  }
  T quickSelect(const int _kth) {
    if ((_cfg & 4) == 0 || _kth > intervalSum(1, _n)) exit(-1);
    T _l = 0, _r = _n + 1;
    while (_l < _r) {
      T _m = (_l + _r) >> 1;
      if (_kth <= intervalSum(1, _m))
        _r = _m;
      else
        _l = _m + 1;
    }
    return _l;
  }
};
void solve() {
  int n;
  string x, y, test;
  cin >> n >> x >> y;
  vector<ll> ans, a(n + 1), b(n + 1);
  segmentTree<ll> seg;
  test = x;
  for (int i = 0; i < n; ++i) {
    a[i + 1] = (x[i] == '1');
    b[i + 1] = (y[i] == '1');
  }
  seg.setUp(a.begin() + 1, a.begin() + n + 1, 4 | 8);
  int l = 1, r = n;
  bool R = 1;
  for (int i = n; i >= 1; --i) {
    if (R) {
      int rVal = seg.intervalSum(r, r) % 2;
      if (rVal == b[i]) {
        --r;
        continue;
      }
      R ^= 1;
      int lVal = seg.intervalSum(l, l) % 2;
      if (lVal == b[i]) {
        ans.push_back(1);
        seg.addOnPos(l, l);
        ans.push_back(i);
        seg.addToInterval(l, r, 1);
      } else {
        ans.push_back(i);
        seg.addToInterval(l, r, 1);
      }
      ++l;
    } else {
      int lVal = seg.intervalSum(l, l) % 2;
      if (lVal == b[i]) {
        ++l;
        continue;
      }
      R ^= 1;
      int rVal = seg.intervalSum(r, r) % 2;
      if (rVal == b[i]) {
        ans.push_back(1);
        seg.addOnPos(r, r);
        ans.push_back(i);
        seg.addToInterval(l, r, 1);
      } else {
        ans.push_back(i);
        seg.addToInterval(l, r, 1);
      }
      --r;
    }
  }
  cout << ans.size() << " ";
  for (auto &it : ans) cout << it << " ";
  cout << "\n";
}
int main() {
  srand(time(0));
  int T = 1;
  if (tc) cin >> T;
  for (int i = 1; i <= T; ++i) {
    solve();
  }
  return 0;
}