#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
string up, dn;
vector<vector<vector<long long int>>> dp;
vector<long long int> waysUp = {3, 3, 1, 2};
vector<long long int> waysDn = {2, 1, 3, 3};
long long int getSubUp(long long int i) {
  string s = up.substr(i - 1, 2);
  long long int mask = 0;
  if (s[0] == 'X') mask |= (1 << 1);
  if (s[1] == 'X') mask |= (1 << 0);
  return mask;
}
long long int getSubDn(long long int i) {
  string s = dn.substr(i - 1, 2);
  long long int mask = 0;
  if (s[0] == 'X') mask |= (1 << 1);
  if (s[1] == 'X') mask |= (1 << 0);
  return mask;
}
void recalc_1(long long int i) {
  long long int maskUp = getSubUp(i);
  long long int maskDn = getSubDn(i);
  for (long long int b11 = 0; b11 < 2; b11++) {
    for (long long int b21 = 0; b21 < 2; b21++) {
      if ((up[i - 1] == '0' || (b11 == 1)) &&
          (dn[i - 1] == '0' || (b21 == 1))) {
        long long int nmaskUp = (b11 << 1) | maskUp;
        long long int nmaskDn = (b21 << 1) | maskDn;
        for (long long int b12 = 0; b12 < 2; b12++) {
          for (long long int b22 = 0; b22 < 2; b22++) {
            long long int updMaskUp = (b12 << 1) | b11;
            long long int updMaskDn = (b22 << 1) | b21;
            dp[i][nmaskUp][nmaskDn] =
                max(dp[i][nmaskUp][nmaskDn], dp[i - 1][updMaskUp][updMaskDn]);
          }
        }
      }
    }
  }
}
void recalc_2(long long int i) {
  long long int BaseMaskUp = getSubUp(i);
  long long int BaseMaskDn = getSubDn(i);
  for (long long int j = 0; j < 4; j++) {
    long long int wup = waysUp[j];
    long long int wdn = waysDn[j];
    if ((BaseMaskUp & wup) == 0 && (BaseMaskDn & wdn) == 0) {
      long long int maskUp = BaseMaskUp | wup;
      long long int maskDn = BaseMaskDn | wdn;
      for (long long int b11 = 0; b11 < 2; b11++) {
        for (long long int b21 = 0; b21 < 2; b21++) {
          if ((((BaseMaskUp >> 1) & 1) == 0 || (b11 == 1)) &&
              (((BaseMaskDn >> 1) & 1) == 0 || (b21 == 1)) &&
              (((wup >> 1) & 1) == 0 || b11 == 0) &&
              (((wdn >> 1) & 1) == 0 || b21 == 0)) {
            long long int nmaskUp = (b11 << 1) | maskUp;
            long long int nmaskDn = (b21 << 1) | maskDn;
            for (long long int b12 = 0; b12 < 2; b12++) {
              for (long long int b22 = 0; b22 < 2; b22++) {
                long long int updMaskUp = (b12 << 1) | b11;
                long long int updMaskDn = (b22 << 1) | b21;
                dp[i][nmaskUp][nmaskDn] =
                    max(dp[i][nmaskUp][nmaskDn],
                        dp[i - 1][updMaskUp][updMaskDn] + 1);
              }
            }
          }
        }
      }
    }
  }
}
signed main() {
  cin >> up >> dn;
  long long int n = up.size();
  if (n <= 1) {
    cout << 0 << "\n";
    return 0;
  }
  dp.resize(n,
            vector<vector<long long int>>(4, vector<long long int>(4, -1e15)));
  long long int baseMaskUp = getSubUp(1);
  long long int baseMaskDn = getSubDn(1);
  dp[1][baseMaskUp][baseMaskDn] = 0;
  for (long long int i = 0; i < 4; i++) {
    long long int wup = waysUp[i];
    long long int wdn = waysDn[i];
    if ((baseMaskUp & wup) == 0 && (baseMaskDn & wdn) == 0) {
      long long int maskUp = baseMaskUp | wup;
      long long int maskDn = baseMaskDn | wdn;
      dp[1][maskUp][maskDn] = 1;
    }
  }
  for (long long int i = 2; i < n; i++) {
    recalc_1(i);
    recalc_2(i);
  }
  long long int ans = 0;
  for (long long int mask1 = 0; mask1 < 4; mask1++) {
    for (long long int mask2 = 0; mask2 < 4; mask2++) {
      ans = max(ans, dp[n - 1][mask1][mask2]);
    }
  }
  cout << ans;
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

Bishwock is a chess figure that consists of three squares resembling an "L-bar". This figure can be rotated by 90, 180 and 270 degrees so it can have four possible states:
    
    
      
    XX   XX   .X   X.  
    X.   .X   XX   XX  
    

Bishwocks don't attack any squares and can even occupy on the adjacent squares as long as they don't occupy the same square. 

Vasya has a board with 2× n squares onto which he wants to put some bishwocks. To his dismay, several squares on this board are already occupied by pawns and Vasya can't put bishwocks there. However, pawns also don't attack bishwocks and they can occupy adjacent squares peacefully.

Knowing the positions of pawns on the board, help Vasya to determine the maximum amount of bishwocks he can put onto the board so that they wouldn't occupy the same squares and wouldn't occupy squares with pawns.

Input

The input contains two nonempty strings that describe Vasya's board. Those strings contain only symbols "0" (zero) that denote the empty squares and symbols "X" (uppercase English letter) that denote the squares occupied by pawns. Strings are nonempty and are of the same length that does not exceed 100.

Output

Output a single integer — the maximum amount of bishwocks that can be placed onto the given board.

Examples

Input

00
00


Output

1

Input

00X00X0XXX0
0XXX0X00X00


Output

4

Input

0X0X0
0X0X0


Output

0

Input

0XXX0
00000


Output

2

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
string up, dn;
vector<vector<vector<long long int>>> dp;
vector<long long int> waysUp = {3, 3, 1, 2};
vector<long long int> waysDn = {2, 1, 3, 3};
long long int getSubUp(long long int i) {
  string s = up.substr(i - 1, 2);
  long long int mask = 0;
  if (s[0] == 'X') mask |= (1 << 1);
  if (s[1] == 'X') mask |= (1 << 0);
  return mask;
}
long long int getSubDn(long long int i) {
  string s = dn.substr(i - 1, 2);
  long long int mask = 0;
  if (s[0] == 'X') mask |= (1 << 1);
  if (s[1] == 'X') mask |= (1 << 0);
  return mask;
}
void recalc_1(long long int i) {
  long long int maskUp = getSubUp(i);
  long long int maskDn = getSubDn(i);
  for (long long int b11 = 0; b11 < 2; b11++) {
    for (long long int b21 = 0; b21 < 2; b21++) {
      if ((up[i - 1] == '0' || (b11 == 1)) &&
          (dn[i - 1] == '0' || (b21 == 1))) {
        long long int nmaskUp = (b11 << 1) | maskUp;
        long long int nmaskDn = (b21 << 1) | maskDn;
        for (long long int b12 = 0; b12 < 2; b12++) {
          for (long long int b22 = 0; b22 < 2; b22++) {
            long long int updMaskUp = (b12 << 1) | b11;
            long long int updMaskDn = (b22 << 1) | b21;
            dp[i][nmaskUp][nmaskDn] =
                max(dp[i][nmaskUp][nmaskDn], dp[i - 1][updMaskUp][updMaskDn]);
          }
        }
      }
    }
  }
}
void recalc_2(long long int i) {
  long long int BaseMaskUp = getSubUp(i);
  long long int BaseMaskDn = getSubDn(i);
  for (long long int j = 0; j < 4; j++) {
    long long int wup = waysUp[j];
    long long int wdn = waysDn[j];
    if ((BaseMaskUp & wup) == 0 && (BaseMaskDn & wdn) == 0) {
      long long int maskUp = BaseMaskUp | wup;
      long long int maskDn = BaseMaskDn | wdn;
      for (long long int b11 = 0; b11 < 2; b11++) {
        for (long long int b21 = 0; b21 < 2; b21++) {
          if ((((BaseMaskUp >> 1) & 1) == 0 || (b11 == 1)) &&
              (((BaseMaskDn >> 1) & 1) == 0 || (b21 == 1)) &&
              (((wup >> 1) & 1) == 0 || b11 == 0) &&
              (((wdn >> 1) & 1) == 0 || b21 == 0)) {
            long long int nmaskUp = (b11 << 1) | maskUp;
            long long int nmaskDn = (b21 << 1) | maskDn;
            for (long long int b12 = 0; b12 < 2; b12++) {
              for (long long int b22 = 0; b22 < 2; b22++) {
                long long int updMaskUp = (b12 << 1) | b11;
                long long int updMaskDn = (b22 << 1) | b21;
                dp[i][nmaskUp][nmaskDn] =
                    max(dp[i][nmaskUp][nmaskDn],
                        dp[i - 1][updMaskUp][updMaskDn] + 1);
              }
            }
          }
        }
      }
    }
  }
}
signed main() {
  cin >> up >> dn;
  long long int n = up.size();
  if (n <= 1) {
    cout << 0 << "\n";
    return 0;
  }
  dp.resize(n,
            vector<vector<long long int>>(4, vector<long long int>(4, -1e15)));
  long long int baseMaskUp = getSubUp(1);
  long long int baseMaskDn = getSubDn(1);
  dp[1][baseMaskUp][baseMaskDn] = 0;
  for (long long int i = 0; i < 4; i++) {
    long long int wup = waysUp[i];
    long long int wdn = waysDn[i];
    if ((baseMaskUp & wup) == 0 && (baseMaskDn & wdn) == 0) {
      long long int maskUp = baseMaskUp | wup;
      long long int maskDn = baseMaskDn | wdn;
      dp[1][maskUp][maskDn] = 1;
    }
  }
  for (long long int i = 2; i < n; i++) {
    recalc_1(i);
    recalc_2(i);
  }
  long long int ans = 0;
  for (long long int mask1 = 0; mask1 < 4; mask1++) {
    for (long long int mask2 = 0; mask2 < 4; mask2++) {
      ans = max(ans, dp[n - 1][mask1][mask2]);
    }
  }
  cout << ans;
  return 0;
}

```