#include <bits/stdc++.h>
using namespace std;
void FAST() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
int Rselect(vector<int>&, int, int, int);
int partition(vector<int>&, int, int);
void scanc(vector<char>& v, long long n) {
  for (int i = 0; i < n; i++) {
    char num;
    cin >> num;
    v.push_back(num);
  }
}
template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& vec) {
  for (auto& i : vec) {
    stream << i << ' ';
  }
  stream << '\n';
  return stream;
}
template <class T>
istream& operator>>(istream& stream, vector<T>& vec) {
  for (auto& i : vec) {
    stream >> i;
  }
  return stream;
}
void scanN(vector<long long>& v, long long n) {
  for (int i = 0; i < n; i++) {
    int num;
    cin >> num;
    v.push_back(num);
  }
}
void scans(vector<string>& v, long long n) {
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    v.push_back(s);
  }
}
long long modfactorial(long long n, long long p) {
  if (n >= p) return 0;
  long long result = 1;
  for (int i = 1; i < n + 1; i++) {
    result = result * i;
    result = result % p;
  }
  return result;
}
long long MI(long long a, long long b, long long s0, long long s1) {
  long long k = b;
  if (b == 0)
    return s0;
  else {
    return MI(b, a % b, s1, s0 - s1 * (a / b));
  }
}
long long choose(long long a, long long b, long long c) {
  if (a < b) return 0;
  long long x = modfactorial(a, c);
  long long y = modfactorial(b, c);
  long long z = modfactorial(a - b, c);
  long long y_ = MI(y, c, 1, 0);
  if (y_ < 0) y_ = y_ + c;
  long long z_ = MI(z, c, 1, 0);
  if (z_ < 0) z_ = z_ + c;
  long long mul = (x * y_) % c;
  mul = (mul * z_) % c;
  return mul;
}
long long modpow(long long n, long long p, long long k) {
  if (p == 0) return 1;
  long long result = 1;
  long long i = 1;
  while (i <= p) {
    result = result * n;
    result = result % k;
  }
  return result;
}
bool isPrime(int a) {
  for (int i = 2; i * i <= a; ++i)
    if (a % i == 0) return false;
  return true;
}
bool useflushdivisible(long long a) {
  cout << a << endl;
  fflush(stdout);
  char sl[10];
  scanf("%s", sl);
  return sl[0] == 'y' || sl[0] == 'Y';
}
long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) n = n / i;
      result = result - result / i;
    }
  }
  if (n > 1) result = result - result / n;
  return result;
}
long long query(long long i, long long j) {
  cout << "? " << i << " " << j << endl;
  fflush(stdout);
  long long num;
  cin >> num;
  return num;
}
void merge(int a[], int head, int mid, int tail, bool increasing = false) {
  int* c = new int[tail - head + 1];
  int i = head, j = mid, k = 0;
  while (k < tail - head + 1) {
    if ((((a[i] > a[j] && increasing) || (a[i] < a[j] && !increasing)) ||
         i == mid) &&
        j != tail + 1) {
      c[k] = a[j];
      j++;
    } else {
      c[k] = a[i];
      i++;
    }
    k++;
  }
  i = 0;
  while (i < k) {
    a[head + i] = c[i];
    i++;
  }
  delete[] c;
}
void mergesort(int a[], int head, int tail) {
  if (head != tail) {
    mergesort(a, head, (tail - head + 1) / 2 + head - 1);
    mergesort(a, (tail - head + 1) / 2 + head, tail);
    merge(a, head, (tail - head + 1) / 2 + head, tail);
  }
}
void sw(int& x, int& y) {
  int temp;
  temp = x;
  x = y;
  y = temp;
  if (x == 1)
    x = 0;
  else
    x = 1;
  if (y == 1)
    y = 0;
  else
    y = 1;
}
void solve() {
  int n, k = 0, a[100000], b[100000], p[200000];
  int be = 0, en;
  char c;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> c;
    if (c == '1')
      a[i] = 1;
    else
      a[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    cin >> c;
    if (c == '1')
      b[i] = 1;
    else
      b[i] = 0;
  }
  int i = n - 1, j = 0, ii = 0, jj = n - 1, tu = 0;
  while (jj > 0) {
    if (tu == 0) {
      if (a[i] != b[jj]) {
        if (a[i] == a[j]) {
          p[k++] = jj + 1;
          tu = 1;
          ii++;
          j = i;
        } else {
          p[k++] = 1;
          if (a[j] == 1)
            a[j] = 0;
          else
            a[j] = 1;
          p[k++] = jj + 1;
          tu = 1;
          ii++;
          j = i;
        }
      } else
        i--;
    } else {
      if (a[ii] == b[jj]) {
        if (a[ii] == a[j]) {
          p[k++] = jj + 1;
          tu = 0;
          i--;
          j = ii;
        } else {
          p[k++] = 1;
          if (a[j] == 1)
            a[j] = 0;
          else
            a[j] = 1;
          p[k++] = jj + 1;
          tu = 0;
          i--;
          j = ii;
        }
      } else
        ii++;
    }
    jj--;
  }
  if (tu == 0 && a[i] != b[jj]) {
    p[k++] = 1;
  }
  if (tu == 1 && a[ii] == b[jj]) {
    p[k++] = 1;
  }
  cout << k << " ";
  for (int i = 0; i < k; i++) cout << p[i] << " ";
  cout << endl;
}
void SOLT() {
  int test;
  cin >> test;
  while (test--) {
    solve();
  }
}
int main() {
  FAST();
  SOLT();
  return 0;
}
int Rselect(vector<int>& v, int i, int l, int r) {
  if (l == r) return v[l];
  int pivot = partition(v, l, r);
  if (pivot == i)
    return v[pivot - 1];
  else if (pivot < i) {
    return Rselect(v, i, pivot, r);
  } else {
    return Rselect(v, i, l, pivot - 2);
  }
}
int partition(vector<int>& v, int l, int r) {
  int pivot_index = rand() % (r - l + 1) + l;
  swap(v[pivot_index], v[l]);
  int i = l + 1, j = l + 1;
  while (j <= r) {
    if (v[j] < v[l]) {
      swap(v[j], v[i]);
      i++;
    }
    j++;
  }
  swap(v[l], v[i - 1]);
  return i;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

This is the hard 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 2n 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≤ 10^5) — 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 10^5.

Output

For each test case, output an integer k (0≤ k≤ 2n), 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void FAST() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
int Rselect(vector<int>&, int, int, int);
int partition(vector<int>&, int, int);
void scanc(vector<char>& v, long long n) {
  for (int i = 0; i < n; i++) {
    char num;
    cin >> num;
    v.push_back(num);
  }
}
template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& vec) {
  for (auto& i : vec) {
    stream << i << ' ';
  }
  stream << '\n';
  return stream;
}
template <class T>
istream& operator>>(istream& stream, vector<T>& vec) {
  for (auto& i : vec) {
    stream >> i;
  }
  return stream;
}
void scanN(vector<long long>& v, long long n) {
  for (int i = 0; i < n; i++) {
    int num;
    cin >> num;
    v.push_back(num);
  }
}
void scans(vector<string>& v, long long n) {
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    v.push_back(s);
  }
}
long long modfactorial(long long n, long long p) {
  if (n >= p) return 0;
  long long result = 1;
  for (int i = 1; i < n + 1; i++) {
    result = result * i;
    result = result % p;
  }
  return result;
}
long long MI(long long a, long long b, long long s0, long long s1) {
  long long k = b;
  if (b == 0)
    return s0;
  else {
    return MI(b, a % b, s1, s0 - s1 * (a / b));
  }
}
long long choose(long long a, long long b, long long c) {
  if (a < b) return 0;
  long long x = modfactorial(a, c);
  long long y = modfactorial(b, c);
  long long z = modfactorial(a - b, c);
  long long y_ = MI(y, c, 1, 0);
  if (y_ < 0) y_ = y_ + c;
  long long z_ = MI(z, c, 1, 0);
  if (z_ < 0) z_ = z_ + c;
  long long mul = (x * y_) % c;
  mul = (mul * z_) % c;
  return mul;
}
long long modpow(long long n, long long p, long long k) {
  if (p == 0) return 1;
  long long result = 1;
  long long i = 1;
  while (i <= p) {
    result = result * n;
    result = result % k;
  }
  return result;
}
bool isPrime(int a) {
  for (int i = 2; i * i <= a; ++i)
    if (a % i == 0) return false;
  return true;
}
bool useflushdivisible(long long a) {
  cout << a << endl;
  fflush(stdout);
  char sl[10];
  scanf("%s", sl);
  return sl[0] == 'y' || sl[0] == 'Y';
}
long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) n = n / i;
      result = result - result / i;
    }
  }
  if (n > 1) result = result - result / n;
  return result;
}
long long query(long long i, long long j) {
  cout << "? " << i << " " << j << endl;
  fflush(stdout);
  long long num;
  cin >> num;
  return num;
}
void merge(int a[], int head, int mid, int tail, bool increasing = false) {
  int* c = new int[tail - head + 1];
  int i = head, j = mid, k = 0;
  while (k < tail - head + 1) {
    if ((((a[i] > a[j] && increasing) || (a[i] < a[j] && !increasing)) ||
         i == mid) &&
        j != tail + 1) {
      c[k] = a[j];
      j++;
    } else {
      c[k] = a[i];
      i++;
    }
    k++;
  }
  i = 0;
  while (i < k) {
    a[head + i] = c[i];
    i++;
  }
  delete[] c;
}
void mergesort(int a[], int head, int tail) {
  if (head != tail) {
    mergesort(a, head, (tail - head + 1) / 2 + head - 1);
    mergesort(a, (tail - head + 1) / 2 + head, tail);
    merge(a, head, (tail - head + 1) / 2 + head, tail);
  }
}
void sw(int& x, int& y) {
  int temp;
  temp = x;
  x = y;
  y = temp;
  if (x == 1)
    x = 0;
  else
    x = 1;
  if (y == 1)
    y = 0;
  else
    y = 1;
}
void solve() {
  int n, k = 0, a[100000], b[100000], p[200000];
  int be = 0, en;
  char c;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> c;
    if (c == '1')
      a[i] = 1;
    else
      a[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    cin >> c;
    if (c == '1')
      b[i] = 1;
    else
      b[i] = 0;
  }
  int i = n - 1, j = 0, ii = 0, jj = n - 1, tu = 0;
  while (jj > 0) {
    if (tu == 0) {
      if (a[i] != b[jj]) {
        if (a[i] == a[j]) {
          p[k++] = jj + 1;
          tu = 1;
          ii++;
          j = i;
        } else {
          p[k++] = 1;
          if (a[j] == 1)
            a[j] = 0;
          else
            a[j] = 1;
          p[k++] = jj + 1;
          tu = 1;
          ii++;
          j = i;
        }
      } else
        i--;
    } else {
      if (a[ii] == b[jj]) {
        if (a[ii] == a[j]) {
          p[k++] = jj + 1;
          tu = 0;
          i--;
          j = ii;
        } else {
          p[k++] = 1;
          if (a[j] == 1)
            a[j] = 0;
          else
            a[j] = 1;
          p[k++] = jj + 1;
          tu = 0;
          i--;
          j = ii;
        }
      } else
        ii++;
    }
    jj--;
  }
  if (tu == 0 && a[i] != b[jj]) {
    p[k++] = 1;
  }
  if (tu == 1 && a[ii] == b[jj]) {
    p[k++] = 1;
  }
  cout << k << " ";
  for (int i = 0; i < k; i++) cout << p[i] << " ";
  cout << endl;
}
void SOLT() {
  int test;
  cin >> test;
  while (test--) {
    solve();
  }
}
int main() {
  FAST();
  SOLT();
  return 0;
}
int Rselect(vector<int>& v, int i, int l, int r) {
  if (l == r) return v[l];
  int pivot = partition(v, l, r);
  if (pivot == i)
    return v[pivot - 1];
  else if (pivot < i) {
    return Rselect(v, i, pivot, r);
  } else {
    return Rselect(v, i, l, pivot - 2);
  }
}
int partition(vector<int>& v, int l, int r) {
  int pivot_index = rand() % (r - l + 1) + l;
  swap(v[pivot_index], v[l]);
  int i = l + 1, j = l + 1;
  while (j <= r) {
    if (v[j] < v[l]) {
      swap(v[j], v[i]);
      i++;
    }
    j++;
  }
  swap(v[l], v[i - 1]);
  return i;
}

```