#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long int power(long long int a, long long int b) {
  if (b == 0) return 1;
  if (b % 2 == 0) return (power((a * a) % 998244353, b / 2)) % 998244353;
  return (a * (power((a * a) % 998244353, b / 2)) % 998244353) % 998244353;
}
long long int modInv(long long int n) { return power(n, 1000000007 - 2); }
long long int nCr(long long int n, long long int r,
                  long long int p = 1000000007) {
  if (r == 0) return 1;
  long long int Fact[n + 1];
  Fact[0] = 1;
  for (long long int i = 1; i <= n; i++) {
    Fact[i] = (Fact[i - 1] * i) % p;
  }
  return (((Fact[n] * modInv(Fact[r])) % 1000000007) *
          (modInv(Fact[n - r]) % 1000000007)) %
         1000000007;
}
double PI = 3.14159265359;
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    long long int n, i;
    cin >> n;
    string a, b;
    cin >> a >> b;
    long long int start = 0, end = n - 1, rev = 0, front = 0, back = n - 1;
    vector<long long int> Ans;
    for (i = n - 1; i >= 0; i--) {
      if (rev) {
        back = start;
        front = end;
      } else {
        back = end;
        front = start;
      }
      long long int d1 = a[back] - '0';
      if (rev) d1 = abs(d1 - 1);
      if (d1 == b[i] - '0') {
        if (rev == 0)
          end--;
        else
          start++;
        continue;
      }
      long long int d = a[front] - '0';
      if (rev) d = abs(d - 1);
      if (d == b[i] - '0') {
        Ans.push_back(1);
        Ans.push_back(i + 1);
      } else {
        Ans.push_back(i + 1);
      }
      if (rev == 0)
        start++;
      else
        end--;
      rev = abs(1 - rev);
    }
    cout << Ans.size() << " ";
    for (i = 0; i < Ans.size(); i++) cout << Ans[i] << " ";
    cout << endl;
  }
}

### Prompt

Your task is to create a CPP solution to the following problem:

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;
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long int power(long long int a, long long int b) {
  if (b == 0) return 1;
  if (b % 2 == 0) return (power((a * a) % 998244353, b / 2)) % 998244353;
  return (a * (power((a * a) % 998244353, b / 2)) % 998244353) % 998244353;
}
long long int modInv(long long int n) { return power(n, 1000000007 - 2); }
long long int nCr(long long int n, long long int r,
                  long long int p = 1000000007) {
  if (r == 0) return 1;
  long long int Fact[n + 1];
  Fact[0] = 1;
  for (long long int i = 1; i <= n; i++) {
    Fact[i] = (Fact[i - 1] * i) % p;
  }
  return (((Fact[n] * modInv(Fact[r])) % 1000000007) *
          (modInv(Fact[n - r]) % 1000000007)) %
         1000000007;
}
double PI = 3.14159265359;
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    long long int n, i;
    cin >> n;
    string a, b;
    cin >> a >> b;
    long long int start = 0, end = n - 1, rev = 0, front = 0, back = n - 1;
    vector<long long int> Ans;
    for (i = n - 1; i >= 0; i--) {
      if (rev) {
        back = start;
        front = end;
      } else {
        back = end;
        front = start;
      }
      long long int d1 = a[back] - '0';
      if (rev) d1 = abs(d1 - 1);
      if (d1 == b[i] - '0') {
        if (rev == 0)
          end--;
        else
          start++;
        continue;
      }
      long long int d = a[front] - '0';
      if (rev) d = abs(d - 1);
      if (d == b[i] - '0') {
        Ans.push_back(1);
        Ans.push_back(i + 1);
      } else {
        Ans.push_back(i + 1);
      }
      if (rev == 0)
        start++;
      else
        end--;
      rev = abs(1 - rev);
    }
    cout << Ans.size() << " ";
    for (i = 0; i < Ans.size(); i++) cout << Ans[i] << " ";
    cout << endl;
  }
}

```