#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void ckmax(T &x, T y) {
  x = x < y ? y : x;
  return;
}
template <typename T>
inline void ckmin(T &x, T y) {
  x = x < y ? x : y;
  return;
}
inline long long read() {
  long long res = 0, f = 1;
  char k;
  while (!isdigit(k = getchar()))
    if (k == '-') f = -1;
  while (isdigit(k)) res = res * 10 + k - '0', k = getchar();
  return res * f;
}
namespace Output {
char OPUT[100];
inline void print(long long x) {
  if (!x) return putchar('0'), putchar('\n'), void();
  if (x < 0) putchar('-'), x = -x;
  long long cnt = 0;
  while (x) OPUT[++cnt] = x % 10, x /= 10;
  for (register long long i = cnt; i >= 1; --i) putchar(OPUT[i] + '0');
  putchar('\n');
  return;
}
}  // namespace Output
using namespace Output;
inline long long gcd(long long x, long long y) {
  return (!y) ? x : gcd(y, x % y);
}
inline long long lcm(long long x, long long y) { return x / gcd(x, y) * y; }
const long long mod = 998244353;
inline long long add(long long x, long long y, long long Mod = mod) {
  return x + y >= Mod ? x + y - Mod : x + y;
}
inline long long del(long long x, long long y, long long Mod = mod) {
  return x - y < 0 ? x - y + Mod : x - y;
}
inline long long mul(long long x, long long y, long long Mod = mod) {
  return x * y - x * y / Mod * Mod;
}
inline void ckadd(long long &x, long long y, long long Mod = mod) {
  x = x + y >= Mod ? x + y - Mod : x + y;
}
inline void ckdel(long long &x, long long y, long long Mod = mod) {
  x = x - y < 0 ? x - y + Mod : x - y;
}
inline void ckmul(long long &x, long long y, long long Mod = mod) {
  x = x * y - x * y / Mod * Mod;
}
inline long long ksm(long long x, long long y, long long Mod = mod) {
  long long res = 1;
  for (; y; y >>= 1, ckmul(x, x, Mod))
    if (y & 1) ckmul(res, x, Mod);
  return res;
}
inline void approx(long long val, long long Mod = mod, long long lim = 1e5) {
  long long x = val, y = Mod, a = 1, b = 0;
  while (x > lim) {
    swap(x, y);
    swap(a, b);
    a -= x / y * b;
    x %= y;
  }
  cout << x << "/" << a << endl;
  return;
}
const double pi = acos(-1);
struct Complex {
  double x, y;
  Complex() {}
  Complex(double xx, double yy) {
    x = xx;
    y = yy;
    return;
  }
  Complex operator+(const Complex &a) const {
    return Complex(x + a.x, y + a.y);
  }
  Complex operator-(const Complex &a) const {
    return Complex(x - a.x, y - a.y);
  }
  Complex operator*(const Complex &a) const {
    return Complex(x * a.x - y * a.y, x * a.y + y * a.x);
  }
};
inline pair<Complex, Complex> square_root(Complex a) {
  double len = sqrt(a.x * a.x + a.y * a.y);
  len = sqrt(len);
  double ang = atan2(a.y, a.x), a1 = ang / 2 + pi, a2 = ang / 2;
  if (a2 < 0) a2 += 2 * pi;
  return make_pair(Complex(cos(a1) * len, sin(a1) * len),
                   Complex(cos(a2) * len, sin(a2) * len));
}
inline double cross(Complex a, Complex b) { return a.x * b.y - a.y * b.x; }
struct fractor {
  long long x, y;
  fractor() {}
  fractor(long long xx, long long yy) {
    x = xx;
    y = yy;
    return;
  }
  fractor operator+(const fractor &a) const {
    long long mu = lcm(y, a.y), zi = x * (mu / y) + a.x * (mu / a.y);
    long long g = gcd(mu, zi);
    return fractor(zi / g, mu / g);
  }
  fractor operator*(const fractor &a) const {
    long long gg = gcd(y, a.x) * gcd(x, a.y);
    return fractor(x * a.x / gg, y * a.y / gg);
  }
  bool operator<(const fractor &a) const {
    long long da = x / y, db = a.x / a.y;
    if (da ^ db) return da < db;
    fractor t1 = fractor(x - y * da, y), t2 = fractor(a.x - a.y * db, a.y);
    return t1.x * t2.y < t2.x * t1.y;
  }
};
const long long N = 1e5 + 10;
long long n, ans, a[N], dp[N];
char s1[100010], s2[100010];
inline long long random(long long x) { return 1ll * rand() * rand() % x + 1; }
inline long long random(long long l, long long r) {
  return 1ll * rand() * rand() % (r - l + 1) + l;
}
signed main() {
  srand((unsigned)time(0));
  long long T = read();
  while (T--) {
    n = read(), ans = 0;
    scanf("%s%s", s1 + 1, s2 + 1);
    for (register long long i = 1; i <= n; ++i)
      a[i] = s1[i] - '0' + s2[i] - '0', dp[i] = 0;
    if (n == 1) {
      if (a[1] == 0)
        print(1);
      else if (a[1] == 1)
        print(2);
      else
        print(0);
      continue;
    }
    ans = (a[1] == 1) * 2;
    for (register long long i = 2; i <= n; ++i) {
      if (a[i] == 2) {
        if (a[i - 1] == 0 && dp[i - 1] == 0) dp[i] = 1, ans += 2;
      } else if (a[i] == 1) {
        ans += 2;
        if (a[i - 1] == 0 && !dp[i - 1]) ans += 1;
      } else {
        if (a[i - 1] == 2 && dp[i - 1] == 0)
          dp[i] = 1, ans += 2;
        else if (a[i - 1] == 0 && !dp[i - 1])
          ans += 1;
      }
    }
    if (!dp[n] && a[n] == 0) ++ans;
    print(ans);
  }
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

A binary string is a string that consists of characters 0 and 1. A bi-table is a table that has exactly two rows of equal length, each being a binary string.

Let \operatorname{MEX} of a bi-table be the smallest digit among 0, 1, or 2 that does not occur in the bi-table. For example, \operatorname{MEX} for \begin{bmatrix} 0011\\\ 1010 \end{bmatrix} is 2, because 0 and 1 occur in the bi-table at least once. \operatorname{MEX} for \begin{bmatrix} 111\\\ 111 \end{bmatrix} is 0, because 0 and 2 do not occur in the bi-table, and 0 < 2.

You are given a bi-table with n columns. You should cut it into any number of bi-tables (each consisting of consecutive columns) so that each column is in exactly one bi-table. It is possible to cut the bi-table into a single bi-table — the whole bi-table.

What is the maximal sum of \operatorname{MEX} of all resulting bi-tables can be?

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Description of the test cases follows.

The first line of the description of each test case contains a single integer n (1 ≤ n ≤ 10^5) — the number of columns in the bi-table.

Each of the next two lines contains a binary string of length n — the rows of the bi-table.

It's guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case print a single integer — the maximal sum of \operatorname{MEX} of all bi-tables that it is possible to get by cutting the given bi-table optimally.

Example

Input


4
7
0101000
1101100
5
01100
10101
2
01
01
6
000000
111111


Output


8
8
2
12

Note

In the first test case you can cut the bi-table as follows:

  * \begin{bmatrix} 0\\\ 1 \end{bmatrix}, its \operatorname{MEX} is 2.
  * \begin{bmatrix} 10\\\ 10 \end{bmatrix}, its \operatorname{MEX} is 2.
  * \begin{bmatrix} 1\\\ 1 \end{bmatrix}, its \operatorname{MEX} is 0.
  * \begin{bmatrix} 0\\\ 1 \end{bmatrix}, its \operatorname{MEX} is 2.
  * \begin{bmatrix} 0\\\ 0 \end{bmatrix}, its \operatorname{MEX} is 1.
  * \begin{bmatrix} 0\\\ 0 \end{bmatrix}, its \operatorname{MEX} is 1.



The sum of \operatorname{MEX} is 8.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void ckmax(T &x, T y) {
  x = x < y ? y : x;
  return;
}
template <typename T>
inline void ckmin(T &x, T y) {
  x = x < y ? x : y;
  return;
}
inline long long read() {
  long long res = 0, f = 1;
  char k;
  while (!isdigit(k = getchar()))
    if (k == '-') f = -1;
  while (isdigit(k)) res = res * 10 + k - '0', k = getchar();
  return res * f;
}
namespace Output {
char OPUT[100];
inline void print(long long x) {
  if (!x) return putchar('0'), putchar('\n'), void();
  if (x < 0) putchar('-'), x = -x;
  long long cnt = 0;
  while (x) OPUT[++cnt] = x % 10, x /= 10;
  for (register long long i = cnt; i >= 1; --i) putchar(OPUT[i] + '0');
  putchar('\n');
  return;
}
}  // namespace Output
using namespace Output;
inline long long gcd(long long x, long long y) {
  return (!y) ? x : gcd(y, x % y);
}
inline long long lcm(long long x, long long y) { return x / gcd(x, y) * y; }
const long long mod = 998244353;
inline long long add(long long x, long long y, long long Mod = mod) {
  return x + y >= Mod ? x + y - Mod : x + y;
}
inline long long del(long long x, long long y, long long Mod = mod) {
  return x - y < 0 ? x - y + Mod : x - y;
}
inline long long mul(long long x, long long y, long long Mod = mod) {
  return x * y - x * y / Mod * Mod;
}
inline void ckadd(long long &x, long long y, long long Mod = mod) {
  x = x + y >= Mod ? x + y - Mod : x + y;
}
inline void ckdel(long long &x, long long y, long long Mod = mod) {
  x = x - y < 0 ? x - y + Mod : x - y;
}
inline void ckmul(long long &x, long long y, long long Mod = mod) {
  x = x * y - x * y / Mod * Mod;
}
inline long long ksm(long long x, long long y, long long Mod = mod) {
  long long res = 1;
  for (; y; y >>= 1, ckmul(x, x, Mod))
    if (y & 1) ckmul(res, x, Mod);
  return res;
}
inline void approx(long long val, long long Mod = mod, long long lim = 1e5) {
  long long x = val, y = Mod, a = 1, b = 0;
  while (x > lim) {
    swap(x, y);
    swap(a, b);
    a -= x / y * b;
    x %= y;
  }
  cout << x << "/" << a << endl;
  return;
}
const double pi = acos(-1);
struct Complex {
  double x, y;
  Complex() {}
  Complex(double xx, double yy) {
    x = xx;
    y = yy;
    return;
  }
  Complex operator+(const Complex &a) const {
    return Complex(x + a.x, y + a.y);
  }
  Complex operator-(const Complex &a) const {
    return Complex(x - a.x, y - a.y);
  }
  Complex operator*(const Complex &a) const {
    return Complex(x * a.x - y * a.y, x * a.y + y * a.x);
  }
};
inline pair<Complex, Complex> square_root(Complex a) {
  double len = sqrt(a.x * a.x + a.y * a.y);
  len = sqrt(len);
  double ang = atan2(a.y, a.x), a1 = ang / 2 + pi, a2 = ang / 2;
  if (a2 < 0) a2 += 2 * pi;
  return make_pair(Complex(cos(a1) * len, sin(a1) * len),
                   Complex(cos(a2) * len, sin(a2) * len));
}
inline double cross(Complex a, Complex b) { return a.x * b.y - a.y * b.x; }
struct fractor {
  long long x, y;
  fractor() {}
  fractor(long long xx, long long yy) {
    x = xx;
    y = yy;
    return;
  }
  fractor operator+(const fractor &a) const {
    long long mu = lcm(y, a.y), zi = x * (mu / y) + a.x * (mu / a.y);
    long long g = gcd(mu, zi);
    return fractor(zi / g, mu / g);
  }
  fractor operator*(const fractor &a) const {
    long long gg = gcd(y, a.x) * gcd(x, a.y);
    return fractor(x * a.x / gg, y * a.y / gg);
  }
  bool operator<(const fractor &a) const {
    long long da = x / y, db = a.x / a.y;
    if (da ^ db) return da < db;
    fractor t1 = fractor(x - y * da, y), t2 = fractor(a.x - a.y * db, a.y);
    return t1.x * t2.y < t2.x * t1.y;
  }
};
const long long N = 1e5 + 10;
long long n, ans, a[N], dp[N];
char s1[100010], s2[100010];
inline long long random(long long x) { return 1ll * rand() * rand() % x + 1; }
inline long long random(long long l, long long r) {
  return 1ll * rand() * rand() % (r - l + 1) + l;
}
signed main() {
  srand((unsigned)time(0));
  long long T = read();
  while (T--) {
    n = read(), ans = 0;
    scanf("%s%s", s1 + 1, s2 + 1);
    for (register long long i = 1; i <= n; ++i)
      a[i] = s1[i] - '0' + s2[i] - '0', dp[i] = 0;
    if (n == 1) {
      if (a[1] == 0)
        print(1);
      else if (a[1] == 1)
        print(2);
      else
        print(0);
      continue;
    }
    ans = (a[1] == 1) * 2;
    for (register long long i = 2; i <= n; ++i) {
      if (a[i] == 2) {
        if (a[i - 1] == 0 && dp[i - 1] == 0) dp[i] = 1, ans += 2;
      } else if (a[i] == 1) {
        ans += 2;
        if (a[i - 1] == 0 && !dp[i - 1]) ans += 1;
      } else {
        if (a[i - 1] == 2 && dp[i - 1] == 0)
          dp[i] = 1, ans += 2;
        else if (a[i - 1] == 0 && !dp[i - 1])
          ans += 1;
      }
    }
    if (!dp[n] && a[n] == 0) ++ans;
    print(ans);
  }
  return 0;
}

```