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>
using namespace std;
int64_t Seive(long long n, bool *p) {
  long long i, j;
  for (i = 2; i <= n; i++) {
    if (p[i] == 1)
      for (j = i * i; j <= n; j += i) {
        p[j] = 0;
      }
  }
  p[1] = 0;
  return 0;
}
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long modexp(long long x, long long y) {
  if (y == 0)
    return 1;
  else if (y % 2 == 0) {
    return modexp((x * x) % (long long)(1e9 + 7), y / 2);
  } else {
    return (x * modexp((x * x) % (long long)(1e9 + 7), (y - 1) / 2)) %
           (long long)(1e9 + 7);
  }
}
long long fact(long long n) {
  long long f = 1;
  for (long long i = 2; i <= n; i++) {
    f = (i % (long long)(1e9 + 7) * f % (long long)(1e9 + 7)) %
        (long long)(1e9 + 7);
  }
  return f;
}
long long nCr(long long n, long long r) {
  return (fact(n) * modexp((fact(n - r) * fact(r)) % (long long)(1e9 + 7),
                           (long long)(1e9 + 7) - 2)) %
         (long long)(1e9 + 7);
}
void showlist(list<int64_t> g) {
  list<int64_t>::iterator it;
  for (it = g.begin(); it != g.end(); ++it) cout << *it << " ";
  cout << '\n';
}
void swap(int64_t &a, int64_t &b) {
  int64_t t;
  t = a;
  a = b;
  b = t;
}
void build(int64_t l, int64_t r, int64_t i) {
  if (l == r) {
  } else {
    int64_t mid = (l + r) / 2;
    build(l, mid, 2 * i);
    build(mid + 1, r, 2 * i + 1);
  }
}
void update(int64_t p, int64_t l, int64_t r, int64_t i) {
  if (l == r) {
  } else {
    int64_t mid = (l + r) / 2;
    if (p <= mid) {
      update(p, l, mid, 2 * i);
    } else {
      update(p, mid + 1, r, 2 * i + 1);
    }
  }
}
void query(int64_t y, int64_t z, int64_t l, int64_t r, int64_t i) {
  if (y <= l && z >= r) {
  } else {
    int64_t mid = (l + r) / 2;
    if (z <= mid) {
      query(y, z, l, mid, 2 * i);
    } else if (y > mid) {
      query(y, z, mid + 1, r, 2 * i + 1);
    } else {
      query(y, z, l, mid, 2 * i);
      query(y, z, mid + 1, r, 2 * i + 1);
    }
  }
}
void make_set(int64_t v) {}
int64_t find_set(int64_t v) {}
void union_sets(int64_t a, int64_t b) {}
int64_t up_bo(int64_t lo, int64_t hi, int64_t n) {
  while (lo < hi) {
    int64_t mid = (lo + hi) / 2;
    if (mid <= n) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}
bool sortbysec(const pair<int64_t, int64_t> &a,
               const pair<int64_t, int64_t> &b) {
  if (a.second < b.second || (a.second == b.second && a.first > b.first))
    return true;
  else
    return false;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int64_t T, hh = 0;
  cin >> T;
  while (T--) {
    int64_t n, i, k;
    cin >> n;
    string a, b;
    cin >> a >> b;
    vector<int64_t> ans;
    for (i = 0; i < n; i++) {
      if (i % 2 == 0) {
        k = i / 2;
      } else {
        k = n - i / 2 - 1;
      }
      a[k] = ((a[k] - '0') + i) % 2 + '0';
      if (a[k] == b[n - i - 1]) {
        ans.push_back(1);
      }
      ans.push_back(n - i);
    }
    cout << ans.size() << " ";
    for (i = 0; i < ans.size(); i++) {
      cout << ans[i] << " ";
    }
    cout << "\n";
  }
  return 0;
}