#include <bits/stdc++.h>
using namespace std;
class MPI {
 public:
  vector<long long int> MPI_VALUE;
  bool MPI_SIGN;
  MPI(const string &mpi_s) {
    MPI_SIGN = false;
    if (((long long int)(mpi_s).size())) {
      if (mpi_s[0] == '-') MPI_SIGN = true;
      for (long long int i = ((long long int)(mpi_s).size()) - 1;
           ((mpi_s[0] == '-') ? 1 : 0) <= i; i -= 6) {
        long long int mpi_sum = 0;
        long long int mpi_base = 1;
        for (long long int j = 0; j < ((long long int)(6)); j++)
          if (((mpi_s[0] == '-') ? 1 : 0) <= i - j) {
            mpi_sum += (mpi_s[i - j] - '0') * mpi_base;
            mpi_base *= 10;
          }
        MPI_VALUE.push_back(mpi_sum);
      }
    }
    mpi_reform(*this);
  }
  MPI(const vector<long long int> &mpi_vec) {
    MPI_SIGN = false;
    MPI_VALUE = mpi_vec;
    mpi_reform(*this);
  }
  MPI(int mpi_val) {
    MPI_SIGN = false;
    if (mpi_val < 0) {
      mpi_val = -mpi_val;
      MPI_SIGN = true;
    }
    while (mpi_val) {
      MPI_VALUE.push_back(mpi_val % 1000000);
      mpi_val /= 1000000;
    }
    mpi_reform(*this);
  }
  MPI(long long int mpi_val) {
    MPI_SIGN = false;
    if (mpi_val < 0) {
      mpi_val = -mpi_val;
      MPI_SIGN = true;
    }
    while (mpi_val) {
      MPI_VALUE.push_back(mpi_val % 1000000);
      mpi_val /= 1000000;
    }
    mpi_reform(*this);
  }
  MPI(bool mpi_need0, bool mpi_need1) { MPI_SIGN = false; }
  MPI() {
    MPI_SIGN = false;
    MPI_VALUE.push_back(0);
  }
  string to_string() const {
    string mpi_res = "";
    long long int mpi_p10[6 + 1];
    for (long long int i = 0; i < ((long long int)(6 + 1)); i++)
      mpi_p10[i] = (i) ? (mpi_p10[i - 1] * 10) : 1;
    for (long long int i = ((long long int)(MPI_VALUE).size()) - 1; 0 <= i; i--)
      for (long long int j = 0; j < ((long long int)(6)); j++) {
        long long int mpi_tmp =
            (MPI_VALUE[i] % mpi_p10[6 - j]) / mpi_p10[6 - j - 1];
        if (((long long int)(mpi_res).size()) || mpi_tmp)
          mpi_res += string(1, '0' + mpi_tmp);
      }
    if (((long long int)(mpi_res).size()) == 0)
      mpi_res += "0";
    else if (MPI_SIGN)
      mpi_res = "-" + mpi_res;
    return mpi_res;
  }
  long long int to_long() const {
    long long int mpi_res = 0;
    long long int mpi_base = 1;
    for (long long int i = 0;
         i < ((long long int)(((long long int)(MPI_VALUE).size()))); i++) {
      mpi_res += MPI_VALUE[i] * mpi_base;
      mpi_base *= 1000000;
    }
    if (MPI_SIGN) mpi_res = -mpi_res;
    return mpi_res;
  }
  long long int size() const {
    long long int mpi_res = (((long long int)(MPI_VALUE).size()) - 1) * 6;
    long long int mpi_tmp = MPI_VALUE.back();
    while (mpi_tmp) {
      mpi_res++;
      mpi_tmp /= 10;
    }
    return mpi_res;
  }
  static MPI mpi_abs_add(const MPI &mpi0, const MPI &mpi1) {
    MPI mpi_res(false, false);
    long long int carry = 0;
    for (long long int i = 0;
         i < ((long long int)(max(((long long int)(mpi0.MPI_VALUE).size()),
                                  ((long long int)(mpi1.MPI_VALUE).size()))));
         i++) {
      long long int mpi_t0 = (i < ((long long int)(mpi0.MPI_VALUE).size()))
                                 ? (mpi0.MPI_VALUE[i])
                                 : 0;
      long long int mpi_t1 = (i < ((long long int)(mpi1.MPI_VALUE).size()))
                                 ? (mpi1.MPI_VALUE[i])
                                 : 0;
      long long int mpi_t = mpi_t0 + mpi_t1 + carry;
      mpi_res.MPI_VALUE.push_back(mpi_t % 1000000);
      carry = mpi_t / 1000000;
    }
    if (carry) mpi_res.MPI_VALUE.push_back(carry);
    mpi_reform(mpi_res);
    return mpi_res;
  }
  static MPI mpi_abs_sub_sub(const MPI &mpi0, const MPI &mpi1) {
    MPI mpi_res(false, false);
    mpi_res.MPI_VALUE = mpi0.MPI_VALUE;
    long long int carry = 0;
    for (long long int i = 0;
         i < ((long long int)(mpi1.MPI_VALUE).size()) || carry; i++) {
      mpi_res.MPI_VALUE[i] -= carry;
      carry = 0;
      if (i < ((long long int)(mpi1.MPI_VALUE).size()))
        mpi_res.MPI_VALUE[i] = mpi_res.MPI_VALUE[i] - mpi1.MPI_VALUE[i];
      if (mpi_res.MPI_VALUE[i] < 0) {
        carry++;
        mpi_res.MPI_VALUE[i] += 1000000;
      }
    }
    mpi_reform(mpi_res);
    return mpi_res;
  }
  static MPI mpi_abs_sub(const MPI &mpi0, const MPI &mpi1) {
    if (!mpi_abs_gt(mpi0, mpi1)) return mpi_abs_sub_sub(mpi0, mpi1);
    MPI mpi_res = mpi_abs_sub_sub(mpi1, mpi0);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  static MPI mpi_abs_mul(const MPI &mpi0, const MPI &mpi1) {
    MPI mpi_res(false, false);
    mpi_res.MPI_VALUE =
        vector<long long int>(((long long int)(mpi0.MPI_VALUE).size()) +
                                  ((long long int)(mpi1.MPI_VALUE).size()),
                              0);
    for (long long int i = 0;
         i < ((long long int)(((long long int)(mpi0.MPI_VALUE).size()))); i++)
      if (mpi0.MPI_VALUE[i]) {
        for (long long int j = 0;
             j < ((long long int)(((long long int)(mpi1.MPI_VALUE).size())));
             j++) {
          mpi_res.MPI_VALUE[i + j] += mpi0.MPI_VALUE[i] * mpi1.MPI_VALUE[j];
        }
      }
    mpi_add_mul_reform(mpi_res);
    return mpi_res;
  }
  MPI operator+(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_add(*this, mpi_var);
    if (!b0 && b1) return mpi_abs_sub(*this, mpi_var);
    if (b0 && !b1) return mpi_abs_sub(mpi_var, *this);
    MPI mpi_res = mpi_abs_add(*this, mpi_var);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  MPI operator-(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_sub(*this, mpi_var);
    if (!b0 && b1) return mpi_abs_add(*this, mpi_var);
    if (b0 && b1) return mpi_abs_sub(mpi_var, *this);
    MPI mpi_res = mpi_abs_add(*this, mpi_var);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  MPI operator*(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (b0 && b1) return mpi_abs_mul(*this, mpi_var);
    if (!b0 && !b1) return mpi_abs_mul(*this, mpi_var);
    MPI mpi_res = mpi_abs_mul(*this, mpi_var);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  friend std::ostream &operator<<(std::ostream &os, const MPI &mpi_var) {
    os << mpi_var.to_string();
    return os;
  }
  friend std::istream &operator>>(std::istream &is, MPI &mpi_var) {
    string mpi_str;
    is >> mpi_str;
    mpi_var = MPI(mpi_str);
    return is;
  }
  static void mpi_subst(MPI &mpi_from, const MPI &mpi_base,
                        long long int mpi_cons, long long int mpi_shift) {
    long long int carry = 0;
    for (long long int i = 0;
         i + mpi_shift < ((long long int)(mpi_from.MPI_VALUE).size()); i++) {
      mpi_from.MPI_VALUE[mpi_shift + i] -= carry;
      carry = 0;
      if (i < ((long long int)(mpi_base.MPI_VALUE).size())) {
        carry = (mpi_base.MPI_VALUE[i] * mpi_cons) / 1000000;
        mpi_from.MPI_VALUE[mpi_shift + i] -=
            (mpi_base.MPI_VALUE[i] * mpi_cons) % 1000000;
      }
      while (mpi_from.MPI_VALUE[mpi_shift + i] < 0) {
        carry++;
        mpi_from.MPI_VALUE[mpi_shift + i] += 1000000;
      }
    }
  }
  static bool mpi_can_sub(const MPI &mpi_from, const MPI &mpi_base,
                          long long int mpi_cons, long long int mpi_shift) {
    long long int carry = 0;
    for (long long int i = 0;
         i + mpi_shift < ((long long int)(mpi_from.MPI_VALUE).size()); i++) {
      long long int mpi_tmp = carry;
      if (i < ((long long int)(mpi_base.MPI_VALUE).size()))
        mpi_tmp += mpi_base.MPI_VALUE[i] * mpi_cons;
      long long int mpi_dif = (mpi_tmp - mpi_from.MPI_VALUE[i + mpi_shift]);
      if (mpi_dif < 0)
        carry = 0;
      else
        carry = ((mpi_dif % 1000000) ? 1 : 0) + mpi_dif / 1000000;
    }
    return carry == 0;
  }
  static MPI mpi_abs_div_small(const MPI &mpi_den, const MPI &mpi_num,
                               bool is_div) {
    MPI mpi_ans(false, false);
    MPI mpi_rem(mpi_den.MPI_VALUE);
    mpi_ans.MPI_VALUE =
        vector<long long int>(((long long int)(mpi_rem.MPI_VALUE).size()), 0);
    long long int mpi_cons = abs(mpi_num.to_long()), carry = 0;
    for (long long int i = ((long long int)(mpi_rem.MPI_VALUE).size()) - 1;
         0 <= i; i--) {
      mpi_rem.MPI_VALUE[i] += carry * 1000000;
      carry = mpi_rem.MPI_VALUE[i] % mpi_cons;
      mpi_ans.MPI_VALUE[i] = mpi_rem.MPI_VALUE[i] / mpi_cons;
    }
    if (!is_div) return MPI(carry);
    mpi_reform(mpi_ans);
    return mpi_ans;
  }
  static MPI mpi_abs_div(const MPI &mpi_den, const MPI &mpi_num, bool is_div) {
    if (mpi_abs_gt(mpi_num, 1000000))
      return mpi_abs_div_small(mpi_den, mpi_num, is_div);
    MPI mpi_ans(0);
    MPI mpi_rem(mpi_den.MPI_VALUE);
    mpi_ans.MPI_VALUE =
        vector<long long int>(((long long int)(mpi_rem.MPI_VALUE).size()), 0);
    long long int mpi_num_pos = ((long long int)(mpi_num.MPI_VALUE).size()) - 1;
    long long int mpi_num_n = mpi_num.MPI_VALUE[mpi_num_pos];
    if (mpi_num_n * 1000000 < 1000000000000000000ll / 1000000 &&
        1 <= mpi_num_pos) {
      mpi_num_n = mpi_num_n * 1000000 + mpi_num.MPI_VALUE[--mpi_num_pos];
    }
    while (!mpi_abs_gt(mpi_rem, mpi_num)) {
      long long int mpi_rem_pos =
          ((long long int)(mpi_rem.MPI_VALUE).size()) - 1;
      long long int mpi_rem_n = mpi_rem.MPI_VALUE[mpi_rem_pos];
      while (mpi_rem_n < mpi_num_n) {
        mpi_rem_n = mpi_rem_n * 1000000 + mpi_rem.MPI_VALUE[--mpi_rem_pos];
      }
      long long int mpi_tmp = mpi_rem_n / mpi_num_n;
      long long int mpi_dif = mpi_rem_pos - mpi_num_pos;
      while (!mpi_can_sub(mpi_rem, mpi_num, mpi_tmp, mpi_dif)) mpi_tmp--;
      if (mpi_tmp == 0) {
        mpi_rem_n = mpi_rem_n * 1000000 + mpi_rem.MPI_VALUE[--mpi_rem_pos];
        mpi_tmp = mpi_rem_n / mpi_num_n;
        mpi_dif = mpi_rem_pos - mpi_num_pos;
        while (!mpi_can_sub(mpi_rem, mpi_num, mpi_tmp, mpi_dif)) mpi_tmp--;
      }
      mpi_subst(mpi_rem, mpi_num, mpi_tmp, mpi_dif);
      mpi_ans.MPI_VALUE[mpi_dif] += mpi_tmp;
      mpi_reform(mpi_rem);
    }
    if (!is_div) return mpi_rem;
    mpi_add_mul_reform(mpi_ans);
    return mpi_ans;
  }
  MPI operator/(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_div(*this, mpi_var, true);
    if (b0 && b1) return mpi_abs_div(*this, mpi_var, true);
    MPI mpi_res = mpi_abs_div(*this, mpi_var, true);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  MPI operator%(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN;
    if (!b0) return mpi_abs_div(*this, mpi_var, false);
    MPI mpi_res = mpi_abs_div(*this, mpi_var, false);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  bool operator<(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_gt(*this, mpi_var);
    if (b0 && b1) return mpi_abs_sl(*this, mpi_var);
    if (((long long int)(this->MPI_VALUE).size()) == 1 &&
        ((long long int)(mpi_var.MPI_VALUE).size()) == 1) {
      if (this->MPI_VALUE.back() == 0 && mpi_var.MPI_VALUE.back() == 0)
        return true;
    }
    if (b0 && !b1) return true;
    if (!b0 && b1) return false;
  }
  bool operator>(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_sl(*this, mpi_var);
    if (b0 && b1) return mpi_abs_gt(*this, mpi_var);
    if (((long long int)(this->MPI_VALUE).size()) == 1 &&
        ((long long int)(mpi_var.MPI_VALUE).size()) == 1) {
      if (this->MPI_VALUE.back() == 0 && mpi_var.MPI_VALUE.back() == 0)
        return true;
    }
    if (b0 && !b1) return false;
    if (!b0 && b1) return true;
  }
  bool operator==(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (b0 && b1) return mpi_abs_eq(*this, mpi_var);
    if (!b0 && !b1) return mpi_abs_eq(*this, mpi_var);
    if (((long long int)(this->MPI_VALUE).size()) == 1 &&
        ((long long int)(mpi_var.MPI_VALUE).size()) == 1) {
      if (this->MPI_VALUE.back() == 0 && mpi_var.MPI_VALUE.back() == 0)
        return true;
    }
    return false;
  }
  bool operator>=(const MPI &mpi_var) const { return !(*this < mpi_var); }
  bool operator<=(const MPI &mpi_var) const { return !(*this > mpi_var); }
  bool operator!=(const MPI &mpi_var) const { return !(*this == mpi_var); }
  void operator+=(const MPI &mpi_var) { *this = *this + mpi_var; }
  void operator-=(const MPI &mpi_var) { *this = *this - mpi_var; }
  void operator*=(const MPI &mpi_var) { *this = *this * mpi_var; }
  void operator/=(const MPI &mpi_var) { *this = *this / mpi_var; }
  void operator%=(const MPI &mpi_var) { *this = *this % mpi_var; }
  friend bool operator>(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) > mpi_var;
  }
  friend bool operator<(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) < mpi_var;
  }
  friend bool operator>=(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) >= mpi_var;
  }
  friend bool operator<=(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) <= mpi_var;
  }
  friend bool operator!=(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) != mpi_var;
  }
  friend bool operator==(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) == mpi_var;
  }
  MPI operator--() {
    *this = *this - MPI(1);
    return *this;
  }
  MPI operator++() {
    *this = *this + MPI(1);
    return *this;
  }
  MPI operator++(int mpi_i) {
    MPI mpi_res = *this;
    *this = *this + MPI(1);
    return mpi_res;
  }
  MPI operator--(int mpi_i) {
    MPI mpi_res = *this;
    *this = *this - MPI(1);
    return mpi_res;
  }
  MPI operator-() {
    MPI mpi_res = *this;
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  static bool mpi_abs_gt(const MPI &mpi0, const MPI &mpi1) {
    if (((long long int)(mpi0.MPI_VALUE).size()) ==
        ((long long int)(mpi1.MPI_VALUE).size())) {
      for (long long int i = ((long long int)(mpi0.MPI_VALUE).size()) - 1;
           0 <= i; i--) {
        if (mpi0.MPI_VALUE[i] != mpi1.MPI_VALUE[i]) {
          return mpi0.MPI_VALUE[i] < mpi1.MPI_VALUE[i];
        }
      }
    }
    return ((long long int)(mpi0.MPI_VALUE).size()) <
           ((long long int)(mpi1.MPI_VALUE).size());
  }
  static bool mpi_abs_sl(const MPI &mpi0, const MPI &mpi1) {
    if (((long long int)(mpi0.MPI_VALUE).size()) ==
        ((long long int)(mpi1.MPI_VALUE).size())) {
      for (long long int i = ((long long int)(mpi0.MPI_VALUE).size()) - 1;
           0 <= i; i--) {
        if (mpi0.MPI_VALUE[i] != mpi1.MPI_VALUE[i]) {
          return mpi0.MPI_VALUE[i] > mpi1.MPI_VALUE[i];
        }
      }
    }
    return ((long long int)(mpi0.MPI_VALUE).size()) >
           ((long long int)(mpi1.MPI_VALUE).size());
  }
  static bool mpi_abs_eq(const MPI &mpi0, const MPI &mpi1) {
    if (((long long int)(mpi0.MPI_VALUE).size()) !=
        ((long long int)(mpi1.MPI_VALUE).size()))
      return false;
    for (long long int i = 0;
         i < ((long long int)(((long long int)(mpi0.MPI_VALUE).size()))); i++) {
      if (mpi0.MPI_VALUE[i] != mpi1.MPI_VALUE[i]) return false;
    }
    return true;
  }

 private:
  static void mpi_reform_vec(vector<long long int> &mpi_vec) {
    if (((long long int)(mpi_vec).size()) == 0) mpi_vec.push_back(0);
    while (1 < ((long long int)(mpi_vec).size()) && mpi_vec.back() == 0)
      mpi_vec.pop_back();
  }
  static void mpi_add_mul_reform_vec(vector<long long int> &mpi_vec) {
    long long int carry = 0;
    for (long long int i = 0;
         i < ((long long int)(((long long int)(mpi_vec).size()))); i++) {
      mpi_vec[i] += carry;
      carry = mpi_vec[i] / 1000000;
      mpi_vec[i] %= 1000000;
    }
    mpi_vec.push_back(carry);
    mpi_reform_vec(mpi_vec);
  }
  static void mpi_reform(MPI &mpi_var) {
    mpi_reform_vec(mpi_var.MPI_VALUE);
    if (((long long int)(mpi_var.MPI_VALUE).size()) == 1 &&
        mpi_var.MPI_VALUE[0] == 0)
      mpi_var.MPI_SIGN = false;
  }
  static void mpi_add_mul_reform(MPI &mpi_var) {
    mpi_add_mul_reform_vec(mpi_var.MPI_VALUE);
    if (((long long int)(mpi_var.MPI_VALUE).size()) == 1 &&
        mpi_var.MPI_VALUE[0] == 0)
      mpi_var.MPI_SIGN = false;
  }
};
class IRN {
 public:
  MPI IRN_DEN;
  MPI IRN_NUM;
  bool IRN_SIGN;
  IRN() {
    IRN_DEN = 0;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(string irn_str0, string irn_str1) {
    IRN_DEN = irn_str0;
    IRN_NUM = irn_str1;
    IRN_SIGN = false;
    if (IRN_DEN < 0) IRN_SIGN = !IRN_SIGN;
    if (IRN_NUM < 0) IRN_SIGN = !IRN_SIGN;
    IRN_DEN.MPI_SIGN = false;
    IRN_NUM.MPI_SIGN = false;
    irn_reduct(*this);
  }
  IRN(long long int irn_li0, long long int irn_li1) {
    IRN_DEN = irn_li0;
    IRN_NUM = irn_li1;
    IRN_SIGN = false;
    if (IRN_DEN < 0) IRN_SIGN = !IRN_SIGN;
    if (IRN_NUM < 0) IRN_SIGN = !IRN_SIGN;
    IRN_DEN.MPI_SIGN = false;
    IRN_NUM.MPI_SIGN = false;
    irn_reduct(*this);
  }
  IRN(long long int irn_li) {
    IRN_DEN = irn_li;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(string irn_str) {
    IRN_DEN = irn_str;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  string to_string() const {
    if (IRN_SIGN && IRN_DEN != 0)
      return "-" + IRN_DEN.to_string() + "/" + IRN_NUM.to_string();
    return IRN_DEN.to_string() + "/" + IRN_NUM.to_string();
  }
  static MPI irn_mpi_gcd(MPI mpi0, MPI mpi1) {
    MPI mpi_res = 1;
    if (mpi0 == 0 || mpi1 == 0) return MPI(1);
    for (MPI i = 2; i * i <= min(mpi0, mpi1); i++) {
      while (true) {
        if (mpi0 % i != 0) break;
        if (mpi1 % i != 0) break;
        mpi0 /= i;
        mpi1 /= i;
        mpi_res *= i;
      }
      while (mpi0 % i == 0) mpi0 /= i;
      while (mpi1 % i == 0) mpi1 /= i;
    }
    if (mpi0 % min(mpi0, mpi1) != 0) return mpi_res;
    if (mpi1 % min(mpi0, mpi1) != 0) return mpi_res;
    return mpi_res * min(mpi0, mpi1);
  }
  void irn_reduct(IRN &irn_var) const {
    if (irn_var.IRN_DEN == 0) {
      irn_var.IRN_NUM = 1;
      irn_var.IRN_SIGN = false;
      return;
    }
    if (irn_var.IRN_DEN.MPI_SIGN) irn_var.IRN_SIGN = !irn_var.IRN_SIGN;
    if (irn_var.IRN_NUM.MPI_SIGN) irn_var.IRN_SIGN = !irn_var.IRN_SIGN;
    irn_var.IRN_DEN.MPI_SIGN = false;
    irn_var.IRN_NUM.MPI_SIGN = false;
    MPI irn_t = irn_mpi_gcd(irn_var.IRN_NUM, irn_var.IRN_DEN);
    irn_var.IRN_NUM /= irn_t;
    irn_var.IRN_DEN /= irn_t;
  }
  IRN irn_mul(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(1, 1);
    MPI irn_t = irn_mpi_gcd(irn0.IRN_DEN, irn1.IRN_NUM);
    irn_res.IRN_DEN = irn0.IRN_DEN / irn_t;
    irn_res.IRN_NUM = irn1.IRN_NUM / irn_t;
    irn_t = irn_mpi_gcd(irn0.IRN_NUM, irn1.IRN_DEN);
    irn_res.IRN_DEN *= irn1.IRN_DEN / irn_t;
    irn_res.IRN_NUM *= irn0.IRN_NUM / irn_t;
    if (irn1.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn0.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn_res.IRN_DEN == 0) {
      irn_res.IRN_NUM = 1;
      irn_res.IRN_SIGN = false;
    }
    return irn_res;
  }
  IRN irn_div(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(1, 1);
    MPI irn_t = irn_mpi_gcd(irn0.IRN_DEN, irn1.IRN_DEN);
    irn_res.IRN_DEN = irn0.IRN_DEN / irn_t;
    irn_res.IRN_NUM = irn1.IRN_DEN / irn_t;
    irn_t = irn_mpi_gcd(irn0.IRN_NUM, irn1.IRN_NUM);
    irn_res.IRN_DEN *= irn1.IRN_NUM / irn_t;
    irn_res.IRN_NUM *= irn0.IRN_NUM / irn_t;
    if (irn1.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn0.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn_res.IRN_DEN == 0) {
      irn_res.IRN_NUM = 1;
      irn_res.IRN_SIGN = false;
    }
    return irn_res;
  }
  IRN irn_abs_add(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(0);
    if (irn0.IRN_NUM == irn1.IRN_NUM) {
      irn_res.IRN_DEN = irn0.IRN_DEN + irn1.IRN_DEN;
      irn_res.IRN_NUM = irn0.IRN_NUM;
      irn_reduct(irn_res);
      return irn_res;
    }
    irn_res.IRN_NUM = irn0.IRN_NUM * irn1.IRN_NUM;
    irn_res.IRN_DEN = irn0.IRN_DEN * irn1.IRN_NUM;
    irn_res.IRN_DEN += irn1.IRN_DEN * irn0.IRN_NUM;
    irn_reduct(irn_res);
    return irn_res;
  }
  IRN irn_abs_sub(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(0);
    if (irn0.IRN_NUM == irn1.IRN_NUM) {
      irn_res.IRN_DEN = irn0.IRN_DEN - irn1.IRN_DEN;
      irn_res.IRN_NUM = irn0.IRN_NUM;
      irn_reduct(irn_res);
      return irn_res;
    }
    irn_res.IRN_NUM = irn0.IRN_NUM * irn1.IRN_NUM;
    irn_res.IRN_DEN = irn0.IRN_DEN * irn1.IRN_NUM;
    irn_res.IRN_DEN -= irn1.IRN_DEN * irn0.IRN_NUM;
    irn_reduct(irn_res);
    return irn_res;
  }
  IRN irn_add(const IRN &irn0, const IRN &irn1) const {
    if (irn0.IRN_SIGN && irn1.IRN_SIGN) {
      IRN irn_res = irn_abs_add(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
      return irn_res;
    }
    if (!irn0.IRN_SIGN && !irn1.IRN_SIGN) return irn_abs_add(irn0, irn1);
    IRN irn_res;
    if (!irn0.IRN_SIGN && irn1.IRN_SIGN) irn_res = irn_abs_sub(irn0, irn1);
    if (irn0.IRN_SIGN && !irn1.IRN_SIGN) irn_res = irn_abs_sub(irn1, irn0);
    if (irn_res.IRN_DEN.MPI_SIGN) {
      irn_res.IRN_DEN.MPI_SIGN = false;
      irn_res.IRN_SIGN = true;
    }
    return irn_res;
  }
  IRN irn_sub(const IRN &irn0, const IRN &irn1) const {
    if (!irn0.IRN_SIGN && irn1.IRN_SIGN) return irn_abs_add(irn0, irn1);
    if (irn0.IRN_SIGN && !irn1.IRN_SIGN) {
      IRN irn_res = irn_abs_add(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
      return irn_res;
    }
    IRN irn_res;
    if (irn0.IRN_SIGN && irn1.IRN_SIGN) {
      irn_res = irn_abs_sub(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    }
    if (!irn0.IRN_SIGN && !irn1.IRN_SIGN) {
      irn_res = irn_abs_sub(irn0, irn1);
    }
    if (irn_res.IRN_DEN.MPI_SIGN) {
      irn_res.IRN_DEN.MPI_SIGN = false;
      irn_res.IRN_SIGN = true;
    }
    return irn_res;
  }
  bool operator<(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return false;
    bool b0 = this->IRN_SIGN, b1 = irn_var.IRN_SIGN;
    if (b0 && !b1) return true;
    if (!b1 && b0) return false;
    MPI left = this->IRN_DEN * irn_var.IRN_NUM;
    MPI right = irn_var.IRN_DEN * this->IRN_NUM;
    if (!b0 && !b1) return left < right;
    return right < left;
  }
  bool operator>(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return false;
    bool b0 = this->IRN_SIGN, b1 = irn_var.IRN_SIGN;
    if (b0 && !b1) return false;
    if (!b0 && b1) return true;
    MPI left = this->IRN_DEN * irn_var.IRN_NUM;
    MPI right = irn_var.IRN_DEN * this->IRN_NUM;
    if (!b0 && !b1) return left > right;
    return right < left;
  }
  bool operator==(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return true;
    if (this->IRN_SIGN && !irn_var.IRN_SIGN) return false;
    if (!this->IRN_SIGN && irn_var.IRN_SIGN) return false;
    return this->IRN_DEN == irn_var.IRN_DEN && this->IRN_NUM == irn_var.IRN_NUM;
  }
  IRN operator+(const IRN &irn_var) const { return irn_add(*this, irn_var); }
  IRN operator-(const IRN &irn_var) const { return irn_sub(*this, irn_var); }
  IRN operator/(const IRN &irn_var) const { return irn_div(*this, irn_var); }
  IRN operator*(const IRN &irn_var) const { return irn_mul(*this, irn_var); }
  void operator+=(const IRN &irn_var) { *this = *this + irn_var; }
  void operator-=(const IRN &irn_var) { *this = *this - irn_var; }
  void operator*=(const IRN &irn_var) { *this = *this * irn_var; }
  void operator/=(const IRN &irn_var) { *this = *this / irn_var; }
  IRN operator<=(const IRN &irn_var) const { return !(irn_var < *this); }
  IRN operator>=(const IRN &irn_var) const { return !(*this < irn_var); }
  IRN operator!=(const IRN &irn_var) const { return !(*this == irn_var); }
  friend std::ostream &operator<<(std::ostream &os, const IRN &irn_var) {
    os << irn_var.to_string();
    return os;
  }

 private:
};
long long int dp[21][(1ll << (long long int)(21 - 1))];
string base[200005];
long long int cost(string str0, string str1) {
  for (long long int i = ((long long int)(str0).size()); i; i--) {
    if (str0.substr(((long long int)(str0).size()) - i, i) == str1.substr(0, i))
      return ((long long int)(str0).size()) - i;
  }
  return ((long long int)(str0).size());
}
long long int cost(long long int t0, long long int t1, long long int len) {
  for (long long int i = len; i; i--) {
    if ((t0 >> (len - i)) == t1 % (1ll << (long long int)(i))) return len - i;
  }
  return len;
}
long long int con(string str) {
  long long int res = 0;
  for (long long int i = 0;
       i < ((long long int)(((long long int)(str).size()))); i++)
    if (str[i] == '1') res |= (1ll << (long long int)(i));
  return res;
}
int main() {
  long long int n;
  cin >> n;
  for (long long int i = 0; i < ((long long int)(n)); i++) cin >> base[i];
  for (long long int i = 0; i < ((long long int)(21)); i++)
    for (long long int j = 0;
         j < ((long long int)((1ll << (long long int)(21 - 1)))); j++)
      dp[i][j] = (1ll << (long long int)(60));
  ;
  dp[0][0] = 0;
  long long int len = ((long long int)(base[0]).size());
  long long int all = len;
  for (long long int pos = 0; pos < ((long long int)(n)); pos++)
    if (pos) {
      long long int num0 = 0, num1 = 0;
      for (long long int i = 0; i < ((long long int)(len)); i++)
        if (base[pos][i] == '1') num0 |= (1ll << (long long int)(i));
      for (long long int i = 0; i < ((long long int)(len)); i++)
        if (base[pos - 1][i] == '1') num1 |= (1ll << (long long int)(i));
      long long int C = cost(num1, num0, len);
      all += C;
      long long int best = (1ll << (long long int)(60));
      ;
      for (long long int i = 0; i <= len; i++) {
        best = min(best,
                   dp[i][num0 % (1ll << (long long int)(i))] + (len - i) - C);
      }
      for (long long int i = 0; i <= len; i++) {
        dp[i][num1 >> (len - i)] = min(dp[i][num1 >> (len - i)], best);
      }
    }
  long long int res = all;
  for (long long int i = 0; i < ((long long int)(21)); i++)
    for (long long int j = 0;
         j < ((long long int)((1ll << (long long int)(21 - 1)))); j++)
      res = min(res, all + dp[i][j]);
  cout << res << endl;
}

### Prompt

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

On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you.

Let {a1, a2, ..., an} be the given sequence of lines needed to be compressed. Here and below we shall assume that all lines are of the same length and consist only of the digits 0 and 1. Let's define the compression function:

  * f(empty sequence) = empty string 
  * f(s) = s. 
  * f(s1, s2) =  the smallest in length string, which has one of the prefixes equal to s1 and one of the suffixes equal to s2. For example, f(001, 011) = 0011, f(111, 011) = 111011. 
  * f(a1, a2, ..., an) = f(f(a1, a2, an - 1), an). For example, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111. 



Valera faces a real challenge: he should divide the given sequence {a1, a2, ..., an} into two subsequences {b1, b2, ..., bk} and {c1, c2, ..., cm}, m + k = n, so that the value of S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)| took the minimum possible value. Here |p| denotes the length of the string p.

Note that it is not allowed to change the relative order of lines in the subsequences. It is allowed to make one of the subsequences empty. Each string from the initial sequence should belong to exactly one subsequence. Elements of subsequences b and c don't have to be consecutive in the original sequence a, i. e. elements of b and c can alternate in a (see samples 2 and 3).

Help Valera to find the minimum possible value of S.

Input

The first line of input data contains an integer n — the number of strings (1 ≤ n ≤ 2·105). Then on n lines follow elements of the sequence — strings whose lengths are from 1 to 20 characters, consisting only of digits 0 and 1. The i + 1-th input line contains the i-th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.

Output

Print a single number — the minimum possible value of S.

Examples

Input

3
01
10
01


Output

4


Input

4
000
111
110
001


Output

8


Input

5
10101
01010
11111
01000
10010


Output

17

Note

Detailed answers to the tests:

  * The best option is to make one of the subsequences empty, and the second one equal to the whole given sequence. |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4. 
  * The best option is: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8. 
  * The best option is: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 17. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
class MPI {
 public:
  vector<long long int> MPI_VALUE;
  bool MPI_SIGN;
  MPI(const string &mpi_s) {
    MPI_SIGN = false;
    if (((long long int)(mpi_s).size())) {
      if (mpi_s[0] == '-') MPI_SIGN = true;
      for (long long int i = ((long long int)(mpi_s).size()) - 1;
           ((mpi_s[0] == '-') ? 1 : 0) <= i; i -= 6) {
        long long int mpi_sum = 0;
        long long int mpi_base = 1;
        for (long long int j = 0; j < ((long long int)(6)); j++)
          if (((mpi_s[0] == '-') ? 1 : 0) <= i - j) {
            mpi_sum += (mpi_s[i - j] - '0') * mpi_base;
            mpi_base *= 10;
          }
        MPI_VALUE.push_back(mpi_sum);
      }
    }
    mpi_reform(*this);
  }
  MPI(const vector<long long int> &mpi_vec) {
    MPI_SIGN = false;
    MPI_VALUE = mpi_vec;
    mpi_reform(*this);
  }
  MPI(int mpi_val) {
    MPI_SIGN = false;
    if (mpi_val < 0) {
      mpi_val = -mpi_val;
      MPI_SIGN = true;
    }
    while (mpi_val) {
      MPI_VALUE.push_back(mpi_val % 1000000);
      mpi_val /= 1000000;
    }
    mpi_reform(*this);
  }
  MPI(long long int mpi_val) {
    MPI_SIGN = false;
    if (mpi_val < 0) {
      mpi_val = -mpi_val;
      MPI_SIGN = true;
    }
    while (mpi_val) {
      MPI_VALUE.push_back(mpi_val % 1000000);
      mpi_val /= 1000000;
    }
    mpi_reform(*this);
  }
  MPI(bool mpi_need0, bool mpi_need1) { MPI_SIGN = false; }
  MPI() {
    MPI_SIGN = false;
    MPI_VALUE.push_back(0);
  }
  string to_string() const {
    string mpi_res = "";
    long long int mpi_p10[6 + 1];
    for (long long int i = 0; i < ((long long int)(6 + 1)); i++)
      mpi_p10[i] = (i) ? (mpi_p10[i - 1] * 10) : 1;
    for (long long int i = ((long long int)(MPI_VALUE).size()) - 1; 0 <= i; i--)
      for (long long int j = 0; j < ((long long int)(6)); j++) {
        long long int mpi_tmp =
            (MPI_VALUE[i] % mpi_p10[6 - j]) / mpi_p10[6 - j - 1];
        if (((long long int)(mpi_res).size()) || mpi_tmp)
          mpi_res += string(1, '0' + mpi_tmp);
      }
    if (((long long int)(mpi_res).size()) == 0)
      mpi_res += "0";
    else if (MPI_SIGN)
      mpi_res = "-" + mpi_res;
    return mpi_res;
  }
  long long int to_long() const {
    long long int mpi_res = 0;
    long long int mpi_base = 1;
    for (long long int i = 0;
         i < ((long long int)(((long long int)(MPI_VALUE).size()))); i++) {
      mpi_res += MPI_VALUE[i] * mpi_base;
      mpi_base *= 1000000;
    }
    if (MPI_SIGN) mpi_res = -mpi_res;
    return mpi_res;
  }
  long long int size() const {
    long long int mpi_res = (((long long int)(MPI_VALUE).size()) - 1) * 6;
    long long int mpi_tmp = MPI_VALUE.back();
    while (mpi_tmp) {
      mpi_res++;
      mpi_tmp /= 10;
    }
    return mpi_res;
  }
  static MPI mpi_abs_add(const MPI &mpi0, const MPI &mpi1) {
    MPI mpi_res(false, false);
    long long int carry = 0;
    for (long long int i = 0;
         i < ((long long int)(max(((long long int)(mpi0.MPI_VALUE).size()),
                                  ((long long int)(mpi1.MPI_VALUE).size()))));
         i++) {
      long long int mpi_t0 = (i < ((long long int)(mpi0.MPI_VALUE).size()))
                                 ? (mpi0.MPI_VALUE[i])
                                 : 0;
      long long int mpi_t1 = (i < ((long long int)(mpi1.MPI_VALUE).size()))
                                 ? (mpi1.MPI_VALUE[i])
                                 : 0;
      long long int mpi_t = mpi_t0 + mpi_t1 + carry;
      mpi_res.MPI_VALUE.push_back(mpi_t % 1000000);
      carry = mpi_t / 1000000;
    }
    if (carry) mpi_res.MPI_VALUE.push_back(carry);
    mpi_reform(mpi_res);
    return mpi_res;
  }
  static MPI mpi_abs_sub_sub(const MPI &mpi0, const MPI &mpi1) {
    MPI mpi_res(false, false);
    mpi_res.MPI_VALUE = mpi0.MPI_VALUE;
    long long int carry = 0;
    for (long long int i = 0;
         i < ((long long int)(mpi1.MPI_VALUE).size()) || carry; i++) {
      mpi_res.MPI_VALUE[i] -= carry;
      carry = 0;
      if (i < ((long long int)(mpi1.MPI_VALUE).size()))
        mpi_res.MPI_VALUE[i] = mpi_res.MPI_VALUE[i] - mpi1.MPI_VALUE[i];
      if (mpi_res.MPI_VALUE[i] < 0) {
        carry++;
        mpi_res.MPI_VALUE[i] += 1000000;
      }
    }
    mpi_reform(mpi_res);
    return mpi_res;
  }
  static MPI mpi_abs_sub(const MPI &mpi0, const MPI &mpi1) {
    if (!mpi_abs_gt(mpi0, mpi1)) return mpi_abs_sub_sub(mpi0, mpi1);
    MPI mpi_res = mpi_abs_sub_sub(mpi1, mpi0);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  static MPI mpi_abs_mul(const MPI &mpi0, const MPI &mpi1) {
    MPI mpi_res(false, false);
    mpi_res.MPI_VALUE =
        vector<long long int>(((long long int)(mpi0.MPI_VALUE).size()) +
                                  ((long long int)(mpi1.MPI_VALUE).size()),
                              0);
    for (long long int i = 0;
         i < ((long long int)(((long long int)(mpi0.MPI_VALUE).size()))); i++)
      if (mpi0.MPI_VALUE[i]) {
        for (long long int j = 0;
             j < ((long long int)(((long long int)(mpi1.MPI_VALUE).size())));
             j++) {
          mpi_res.MPI_VALUE[i + j] += mpi0.MPI_VALUE[i] * mpi1.MPI_VALUE[j];
        }
      }
    mpi_add_mul_reform(mpi_res);
    return mpi_res;
  }
  MPI operator+(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_add(*this, mpi_var);
    if (!b0 && b1) return mpi_abs_sub(*this, mpi_var);
    if (b0 && !b1) return mpi_abs_sub(mpi_var, *this);
    MPI mpi_res = mpi_abs_add(*this, mpi_var);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  MPI operator-(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_sub(*this, mpi_var);
    if (!b0 && b1) return mpi_abs_add(*this, mpi_var);
    if (b0 && b1) return mpi_abs_sub(mpi_var, *this);
    MPI mpi_res = mpi_abs_add(*this, mpi_var);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  MPI operator*(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (b0 && b1) return mpi_abs_mul(*this, mpi_var);
    if (!b0 && !b1) return mpi_abs_mul(*this, mpi_var);
    MPI mpi_res = mpi_abs_mul(*this, mpi_var);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  friend std::ostream &operator<<(std::ostream &os, const MPI &mpi_var) {
    os << mpi_var.to_string();
    return os;
  }
  friend std::istream &operator>>(std::istream &is, MPI &mpi_var) {
    string mpi_str;
    is >> mpi_str;
    mpi_var = MPI(mpi_str);
    return is;
  }
  static void mpi_subst(MPI &mpi_from, const MPI &mpi_base,
                        long long int mpi_cons, long long int mpi_shift) {
    long long int carry = 0;
    for (long long int i = 0;
         i + mpi_shift < ((long long int)(mpi_from.MPI_VALUE).size()); i++) {
      mpi_from.MPI_VALUE[mpi_shift + i] -= carry;
      carry = 0;
      if (i < ((long long int)(mpi_base.MPI_VALUE).size())) {
        carry = (mpi_base.MPI_VALUE[i] * mpi_cons) / 1000000;
        mpi_from.MPI_VALUE[mpi_shift + i] -=
            (mpi_base.MPI_VALUE[i] * mpi_cons) % 1000000;
      }
      while (mpi_from.MPI_VALUE[mpi_shift + i] < 0) {
        carry++;
        mpi_from.MPI_VALUE[mpi_shift + i] += 1000000;
      }
    }
  }
  static bool mpi_can_sub(const MPI &mpi_from, const MPI &mpi_base,
                          long long int mpi_cons, long long int mpi_shift) {
    long long int carry = 0;
    for (long long int i = 0;
         i + mpi_shift < ((long long int)(mpi_from.MPI_VALUE).size()); i++) {
      long long int mpi_tmp = carry;
      if (i < ((long long int)(mpi_base.MPI_VALUE).size()))
        mpi_tmp += mpi_base.MPI_VALUE[i] * mpi_cons;
      long long int mpi_dif = (mpi_tmp - mpi_from.MPI_VALUE[i + mpi_shift]);
      if (mpi_dif < 0)
        carry = 0;
      else
        carry = ((mpi_dif % 1000000) ? 1 : 0) + mpi_dif / 1000000;
    }
    return carry == 0;
  }
  static MPI mpi_abs_div_small(const MPI &mpi_den, const MPI &mpi_num,
                               bool is_div) {
    MPI mpi_ans(false, false);
    MPI mpi_rem(mpi_den.MPI_VALUE);
    mpi_ans.MPI_VALUE =
        vector<long long int>(((long long int)(mpi_rem.MPI_VALUE).size()), 0);
    long long int mpi_cons = abs(mpi_num.to_long()), carry = 0;
    for (long long int i = ((long long int)(mpi_rem.MPI_VALUE).size()) - 1;
         0 <= i; i--) {
      mpi_rem.MPI_VALUE[i] += carry * 1000000;
      carry = mpi_rem.MPI_VALUE[i] % mpi_cons;
      mpi_ans.MPI_VALUE[i] = mpi_rem.MPI_VALUE[i] / mpi_cons;
    }
    if (!is_div) return MPI(carry);
    mpi_reform(mpi_ans);
    return mpi_ans;
  }
  static MPI mpi_abs_div(const MPI &mpi_den, const MPI &mpi_num, bool is_div) {
    if (mpi_abs_gt(mpi_num, 1000000))
      return mpi_abs_div_small(mpi_den, mpi_num, is_div);
    MPI mpi_ans(0);
    MPI mpi_rem(mpi_den.MPI_VALUE);
    mpi_ans.MPI_VALUE =
        vector<long long int>(((long long int)(mpi_rem.MPI_VALUE).size()), 0);
    long long int mpi_num_pos = ((long long int)(mpi_num.MPI_VALUE).size()) - 1;
    long long int mpi_num_n = mpi_num.MPI_VALUE[mpi_num_pos];
    if (mpi_num_n * 1000000 < 1000000000000000000ll / 1000000 &&
        1 <= mpi_num_pos) {
      mpi_num_n = mpi_num_n * 1000000 + mpi_num.MPI_VALUE[--mpi_num_pos];
    }
    while (!mpi_abs_gt(mpi_rem, mpi_num)) {
      long long int mpi_rem_pos =
          ((long long int)(mpi_rem.MPI_VALUE).size()) - 1;
      long long int mpi_rem_n = mpi_rem.MPI_VALUE[mpi_rem_pos];
      while (mpi_rem_n < mpi_num_n) {
        mpi_rem_n = mpi_rem_n * 1000000 + mpi_rem.MPI_VALUE[--mpi_rem_pos];
      }
      long long int mpi_tmp = mpi_rem_n / mpi_num_n;
      long long int mpi_dif = mpi_rem_pos - mpi_num_pos;
      while (!mpi_can_sub(mpi_rem, mpi_num, mpi_tmp, mpi_dif)) mpi_tmp--;
      if (mpi_tmp == 0) {
        mpi_rem_n = mpi_rem_n * 1000000 + mpi_rem.MPI_VALUE[--mpi_rem_pos];
        mpi_tmp = mpi_rem_n / mpi_num_n;
        mpi_dif = mpi_rem_pos - mpi_num_pos;
        while (!mpi_can_sub(mpi_rem, mpi_num, mpi_tmp, mpi_dif)) mpi_tmp--;
      }
      mpi_subst(mpi_rem, mpi_num, mpi_tmp, mpi_dif);
      mpi_ans.MPI_VALUE[mpi_dif] += mpi_tmp;
      mpi_reform(mpi_rem);
    }
    if (!is_div) return mpi_rem;
    mpi_add_mul_reform(mpi_ans);
    return mpi_ans;
  }
  MPI operator/(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_div(*this, mpi_var, true);
    if (b0 && b1) return mpi_abs_div(*this, mpi_var, true);
    MPI mpi_res = mpi_abs_div(*this, mpi_var, true);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  MPI operator%(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN;
    if (!b0) return mpi_abs_div(*this, mpi_var, false);
    MPI mpi_res = mpi_abs_div(*this, mpi_var, false);
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  bool operator<(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_gt(*this, mpi_var);
    if (b0 && b1) return mpi_abs_sl(*this, mpi_var);
    if (((long long int)(this->MPI_VALUE).size()) == 1 &&
        ((long long int)(mpi_var.MPI_VALUE).size()) == 1) {
      if (this->MPI_VALUE.back() == 0 && mpi_var.MPI_VALUE.back() == 0)
        return true;
    }
    if (b0 && !b1) return true;
    if (!b0 && b1) return false;
  }
  bool operator>(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (!b0 && !b1) return mpi_abs_sl(*this, mpi_var);
    if (b0 && b1) return mpi_abs_gt(*this, mpi_var);
    if (((long long int)(this->MPI_VALUE).size()) == 1 &&
        ((long long int)(mpi_var.MPI_VALUE).size()) == 1) {
      if (this->MPI_VALUE.back() == 0 && mpi_var.MPI_VALUE.back() == 0)
        return true;
    }
    if (b0 && !b1) return false;
    if (!b0 && b1) return true;
  }
  bool operator==(const MPI &mpi_var) const {
    bool b0 = MPI_SIGN, b1 = mpi_var.MPI_SIGN;
    if (b0 && b1) return mpi_abs_eq(*this, mpi_var);
    if (!b0 && !b1) return mpi_abs_eq(*this, mpi_var);
    if (((long long int)(this->MPI_VALUE).size()) == 1 &&
        ((long long int)(mpi_var.MPI_VALUE).size()) == 1) {
      if (this->MPI_VALUE.back() == 0 && mpi_var.MPI_VALUE.back() == 0)
        return true;
    }
    return false;
  }
  bool operator>=(const MPI &mpi_var) const { return !(*this < mpi_var); }
  bool operator<=(const MPI &mpi_var) const { return !(*this > mpi_var); }
  bool operator!=(const MPI &mpi_var) const { return !(*this == mpi_var); }
  void operator+=(const MPI &mpi_var) { *this = *this + mpi_var; }
  void operator-=(const MPI &mpi_var) { *this = *this - mpi_var; }
  void operator*=(const MPI &mpi_var) { *this = *this * mpi_var; }
  void operator/=(const MPI &mpi_var) { *this = *this / mpi_var; }
  void operator%=(const MPI &mpi_var) { *this = *this % mpi_var; }
  friend bool operator>(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) > mpi_var;
  }
  friend bool operator<(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) < mpi_var;
  }
  friend bool operator>=(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) >= mpi_var;
  }
  friend bool operator<=(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) <= mpi_var;
  }
  friend bool operator!=(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) != mpi_var;
  }
  friend bool operator==(long long int mpi_li, const MPI &mpi_var) {
    return MPI(mpi_li) == mpi_var;
  }
  MPI operator--() {
    *this = *this - MPI(1);
    return *this;
  }
  MPI operator++() {
    *this = *this + MPI(1);
    return *this;
  }
  MPI operator++(int mpi_i) {
    MPI mpi_res = *this;
    *this = *this + MPI(1);
    return mpi_res;
  }
  MPI operator--(int mpi_i) {
    MPI mpi_res = *this;
    *this = *this - MPI(1);
    return mpi_res;
  }
  MPI operator-() {
    MPI mpi_res = *this;
    mpi_res.MPI_SIGN = !mpi_res.MPI_SIGN;
    return mpi_res;
  }
  static bool mpi_abs_gt(const MPI &mpi0, const MPI &mpi1) {
    if (((long long int)(mpi0.MPI_VALUE).size()) ==
        ((long long int)(mpi1.MPI_VALUE).size())) {
      for (long long int i = ((long long int)(mpi0.MPI_VALUE).size()) - 1;
           0 <= i; i--) {
        if (mpi0.MPI_VALUE[i] != mpi1.MPI_VALUE[i]) {
          return mpi0.MPI_VALUE[i] < mpi1.MPI_VALUE[i];
        }
      }
    }
    return ((long long int)(mpi0.MPI_VALUE).size()) <
           ((long long int)(mpi1.MPI_VALUE).size());
  }
  static bool mpi_abs_sl(const MPI &mpi0, const MPI &mpi1) {
    if (((long long int)(mpi0.MPI_VALUE).size()) ==
        ((long long int)(mpi1.MPI_VALUE).size())) {
      for (long long int i = ((long long int)(mpi0.MPI_VALUE).size()) - 1;
           0 <= i; i--) {
        if (mpi0.MPI_VALUE[i] != mpi1.MPI_VALUE[i]) {
          return mpi0.MPI_VALUE[i] > mpi1.MPI_VALUE[i];
        }
      }
    }
    return ((long long int)(mpi0.MPI_VALUE).size()) >
           ((long long int)(mpi1.MPI_VALUE).size());
  }
  static bool mpi_abs_eq(const MPI &mpi0, const MPI &mpi1) {
    if (((long long int)(mpi0.MPI_VALUE).size()) !=
        ((long long int)(mpi1.MPI_VALUE).size()))
      return false;
    for (long long int i = 0;
         i < ((long long int)(((long long int)(mpi0.MPI_VALUE).size()))); i++) {
      if (mpi0.MPI_VALUE[i] != mpi1.MPI_VALUE[i]) return false;
    }
    return true;
  }

 private:
  static void mpi_reform_vec(vector<long long int> &mpi_vec) {
    if (((long long int)(mpi_vec).size()) == 0) mpi_vec.push_back(0);
    while (1 < ((long long int)(mpi_vec).size()) && mpi_vec.back() == 0)
      mpi_vec.pop_back();
  }
  static void mpi_add_mul_reform_vec(vector<long long int> &mpi_vec) {
    long long int carry = 0;
    for (long long int i = 0;
         i < ((long long int)(((long long int)(mpi_vec).size()))); i++) {
      mpi_vec[i] += carry;
      carry = mpi_vec[i] / 1000000;
      mpi_vec[i] %= 1000000;
    }
    mpi_vec.push_back(carry);
    mpi_reform_vec(mpi_vec);
  }
  static void mpi_reform(MPI &mpi_var) {
    mpi_reform_vec(mpi_var.MPI_VALUE);
    if (((long long int)(mpi_var.MPI_VALUE).size()) == 1 &&
        mpi_var.MPI_VALUE[0] == 0)
      mpi_var.MPI_SIGN = false;
  }
  static void mpi_add_mul_reform(MPI &mpi_var) {
    mpi_add_mul_reform_vec(mpi_var.MPI_VALUE);
    if (((long long int)(mpi_var.MPI_VALUE).size()) == 1 &&
        mpi_var.MPI_VALUE[0] == 0)
      mpi_var.MPI_SIGN = false;
  }
};
class IRN {
 public:
  MPI IRN_DEN;
  MPI IRN_NUM;
  bool IRN_SIGN;
  IRN() {
    IRN_DEN = 0;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(string irn_str0, string irn_str1) {
    IRN_DEN = irn_str0;
    IRN_NUM = irn_str1;
    IRN_SIGN = false;
    if (IRN_DEN < 0) IRN_SIGN = !IRN_SIGN;
    if (IRN_NUM < 0) IRN_SIGN = !IRN_SIGN;
    IRN_DEN.MPI_SIGN = false;
    IRN_NUM.MPI_SIGN = false;
    irn_reduct(*this);
  }
  IRN(long long int irn_li0, long long int irn_li1) {
    IRN_DEN = irn_li0;
    IRN_NUM = irn_li1;
    IRN_SIGN = false;
    if (IRN_DEN < 0) IRN_SIGN = !IRN_SIGN;
    if (IRN_NUM < 0) IRN_SIGN = !IRN_SIGN;
    IRN_DEN.MPI_SIGN = false;
    IRN_NUM.MPI_SIGN = false;
    irn_reduct(*this);
  }
  IRN(long long int irn_li) {
    IRN_DEN = irn_li;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(string irn_str) {
    IRN_DEN = irn_str;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  string to_string() const {
    if (IRN_SIGN && IRN_DEN != 0)
      return "-" + IRN_DEN.to_string() + "/" + IRN_NUM.to_string();
    return IRN_DEN.to_string() + "/" + IRN_NUM.to_string();
  }
  static MPI irn_mpi_gcd(MPI mpi0, MPI mpi1) {
    MPI mpi_res = 1;
    if (mpi0 == 0 || mpi1 == 0) return MPI(1);
    for (MPI i = 2; i * i <= min(mpi0, mpi1); i++) {
      while (true) {
        if (mpi0 % i != 0) break;
        if (mpi1 % i != 0) break;
        mpi0 /= i;
        mpi1 /= i;
        mpi_res *= i;
      }
      while (mpi0 % i == 0) mpi0 /= i;
      while (mpi1 % i == 0) mpi1 /= i;
    }
    if (mpi0 % min(mpi0, mpi1) != 0) return mpi_res;
    if (mpi1 % min(mpi0, mpi1) != 0) return mpi_res;
    return mpi_res * min(mpi0, mpi1);
  }
  void irn_reduct(IRN &irn_var) const {
    if (irn_var.IRN_DEN == 0) {
      irn_var.IRN_NUM = 1;
      irn_var.IRN_SIGN = false;
      return;
    }
    if (irn_var.IRN_DEN.MPI_SIGN) irn_var.IRN_SIGN = !irn_var.IRN_SIGN;
    if (irn_var.IRN_NUM.MPI_SIGN) irn_var.IRN_SIGN = !irn_var.IRN_SIGN;
    irn_var.IRN_DEN.MPI_SIGN = false;
    irn_var.IRN_NUM.MPI_SIGN = false;
    MPI irn_t = irn_mpi_gcd(irn_var.IRN_NUM, irn_var.IRN_DEN);
    irn_var.IRN_NUM /= irn_t;
    irn_var.IRN_DEN /= irn_t;
  }
  IRN irn_mul(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(1, 1);
    MPI irn_t = irn_mpi_gcd(irn0.IRN_DEN, irn1.IRN_NUM);
    irn_res.IRN_DEN = irn0.IRN_DEN / irn_t;
    irn_res.IRN_NUM = irn1.IRN_NUM / irn_t;
    irn_t = irn_mpi_gcd(irn0.IRN_NUM, irn1.IRN_DEN);
    irn_res.IRN_DEN *= irn1.IRN_DEN / irn_t;
    irn_res.IRN_NUM *= irn0.IRN_NUM / irn_t;
    if (irn1.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn0.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn_res.IRN_DEN == 0) {
      irn_res.IRN_NUM = 1;
      irn_res.IRN_SIGN = false;
    }
    return irn_res;
  }
  IRN irn_div(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(1, 1);
    MPI irn_t = irn_mpi_gcd(irn0.IRN_DEN, irn1.IRN_DEN);
    irn_res.IRN_DEN = irn0.IRN_DEN / irn_t;
    irn_res.IRN_NUM = irn1.IRN_DEN / irn_t;
    irn_t = irn_mpi_gcd(irn0.IRN_NUM, irn1.IRN_NUM);
    irn_res.IRN_DEN *= irn1.IRN_NUM / irn_t;
    irn_res.IRN_NUM *= irn0.IRN_NUM / irn_t;
    if (irn1.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn0.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn_res.IRN_DEN == 0) {
      irn_res.IRN_NUM = 1;
      irn_res.IRN_SIGN = false;
    }
    return irn_res;
  }
  IRN irn_abs_add(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(0);
    if (irn0.IRN_NUM == irn1.IRN_NUM) {
      irn_res.IRN_DEN = irn0.IRN_DEN + irn1.IRN_DEN;
      irn_res.IRN_NUM = irn0.IRN_NUM;
      irn_reduct(irn_res);
      return irn_res;
    }
    irn_res.IRN_NUM = irn0.IRN_NUM * irn1.IRN_NUM;
    irn_res.IRN_DEN = irn0.IRN_DEN * irn1.IRN_NUM;
    irn_res.IRN_DEN += irn1.IRN_DEN * irn0.IRN_NUM;
    irn_reduct(irn_res);
    return irn_res;
  }
  IRN irn_abs_sub(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(0);
    if (irn0.IRN_NUM == irn1.IRN_NUM) {
      irn_res.IRN_DEN = irn0.IRN_DEN - irn1.IRN_DEN;
      irn_res.IRN_NUM = irn0.IRN_NUM;
      irn_reduct(irn_res);
      return irn_res;
    }
    irn_res.IRN_NUM = irn0.IRN_NUM * irn1.IRN_NUM;
    irn_res.IRN_DEN = irn0.IRN_DEN * irn1.IRN_NUM;
    irn_res.IRN_DEN -= irn1.IRN_DEN * irn0.IRN_NUM;
    irn_reduct(irn_res);
    return irn_res;
  }
  IRN irn_add(const IRN &irn0, const IRN &irn1) const {
    if (irn0.IRN_SIGN && irn1.IRN_SIGN) {
      IRN irn_res = irn_abs_add(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
      return irn_res;
    }
    if (!irn0.IRN_SIGN && !irn1.IRN_SIGN) return irn_abs_add(irn0, irn1);
    IRN irn_res;
    if (!irn0.IRN_SIGN && irn1.IRN_SIGN) irn_res = irn_abs_sub(irn0, irn1);
    if (irn0.IRN_SIGN && !irn1.IRN_SIGN) irn_res = irn_abs_sub(irn1, irn0);
    if (irn_res.IRN_DEN.MPI_SIGN) {
      irn_res.IRN_DEN.MPI_SIGN = false;
      irn_res.IRN_SIGN = true;
    }
    return irn_res;
  }
  IRN irn_sub(const IRN &irn0, const IRN &irn1) const {
    if (!irn0.IRN_SIGN && irn1.IRN_SIGN) return irn_abs_add(irn0, irn1);
    if (irn0.IRN_SIGN && !irn1.IRN_SIGN) {
      IRN irn_res = irn_abs_add(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
      return irn_res;
    }
    IRN irn_res;
    if (irn0.IRN_SIGN && irn1.IRN_SIGN) {
      irn_res = irn_abs_sub(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    }
    if (!irn0.IRN_SIGN && !irn1.IRN_SIGN) {
      irn_res = irn_abs_sub(irn0, irn1);
    }
    if (irn_res.IRN_DEN.MPI_SIGN) {
      irn_res.IRN_DEN.MPI_SIGN = false;
      irn_res.IRN_SIGN = true;
    }
    return irn_res;
  }
  bool operator<(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return false;
    bool b0 = this->IRN_SIGN, b1 = irn_var.IRN_SIGN;
    if (b0 && !b1) return true;
    if (!b1 && b0) return false;
    MPI left = this->IRN_DEN * irn_var.IRN_NUM;
    MPI right = irn_var.IRN_DEN * this->IRN_NUM;
    if (!b0 && !b1) return left < right;
    return right < left;
  }
  bool operator>(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return false;
    bool b0 = this->IRN_SIGN, b1 = irn_var.IRN_SIGN;
    if (b0 && !b1) return false;
    if (!b0 && b1) return true;
    MPI left = this->IRN_DEN * irn_var.IRN_NUM;
    MPI right = irn_var.IRN_DEN * this->IRN_NUM;
    if (!b0 && !b1) return left > right;
    return right < left;
  }
  bool operator==(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return true;
    if (this->IRN_SIGN && !irn_var.IRN_SIGN) return false;
    if (!this->IRN_SIGN && irn_var.IRN_SIGN) return false;
    return this->IRN_DEN == irn_var.IRN_DEN && this->IRN_NUM == irn_var.IRN_NUM;
  }
  IRN operator+(const IRN &irn_var) const { return irn_add(*this, irn_var); }
  IRN operator-(const IRN &irn_var) const { return irn_sub(*this, irn_var); }
  IRN operator/(const IRN &irn_var) const { return irn_div(*this, irn_var); }
  IRN operator*(const IRN &irn_var) const { return irn_mul(*this, irn_var); }
  void operator+=(const IRN &irn_var) { *this = *this + irn_var; }
  void operator-=(const IRN &irn_var) { *this = *this - irn_var; }
  void operator*=(const IRN &irn_var) { *this = *this * irn_var; }
  void operator/=(const IRN &irn_var) { *this = *this / irn_var; }
  IRN operator<=(const IRN &irn_var) const { return !(irn_var < *this); }
  IRN operator>=(const IRN &irn_var) const { return !(*this < irn_var); }
  IRN operator!=(const IRN &irn_var) const { return !(*this == irn_var); }
  friend std::ostream &operator<<(std::ostream &os, const IRN &irn_var) {
    os << irn_var.to_string();
    return os;
  }

 private:
};
long long int dp[21][(1ll << (long long int)(21 - 1))];
string base[200005];
long long int cost(string str0, string str1) {
  for (long long int i = ((long long int)(str0).size()); i; i--) {
    if (str0.substr(((long long int)(str0).size()) - i, i) == str1.substr(0, i))
      return ((long long int)(str0).size()) - i;
  }
  return ((long long int)(str0).size());
}
long long int cost(long long int t0, long long int t1, long long int len) {
  for (long long int i = len; i; i--) {
    if ((t0 >> (len - i)) == t1 % (1ll << (long long int)(i))) return len - i;
  }
  return len;
}
long long int con(string str) {
  long long int res = 0;
  for (long long int i = 0;
       i < ((long long int)(((long long int)(str).size()))); i++)
    if (str[i] == '1') res |= (1ll << (long long int)(i));
  return res;
}
int main() {
  long long int n;
  cin >> n;
  for (long long int i = 0; i < ((long long int)(n)); i++) cin >> base[i];
  for (long long int i = 0; i < ((long long int)(21)); i++)
    for (long long int j = 0;
         j < ((long long int)((1ll << (long long int)(21 - 1)))); j++)
      dp[i][j] = (1ll << (long long int)(60));
  ;
  dp[0][0] = 0;
  long long int len = ((long long int)(base[0]).size());
  long long int all = len;
  for (long long int pos = 0; pos < ((long long int)(n)); pos++)
    if (pos) {
      long long int num0 = 0, num1 = 0;
      for (long long int i = 0; i < ((long long int)(len)); i++)
        if (base[pos][i] == '1') num0 |= (1ll << (long long int)(i));
      for (long long int i = 0; i < ((long long int)(len)); i++)
        if (base[pos - 1][i] == '1') num1 |= (1ll << (long long int)(i));
      long long int C = cost(num1, num0, len);
      all += C;
      long long int best = (1ll << (long long int)(60));
      ;
      for (long long int i = 0; i <= len; i++) {
        best = min(best,
                   dp[i][num0 % (1ll << (long long int)(i))] + (len - i) - C);
      }
      for (long long int i = 0; i <= len; i++) {
        dp[i][num1 >> (len - i)] = min(dp[i][num1 >> (len - i)], best);
      }
    }
  long long int res = all;
  for (long long int i = 0; i < ((long long int)(21)); i++)
    for (long long int j = 0;
         j < ((long long int)((1ll << (long long int)(21 - 1)))); j++)
      res = min(res, all + dp[i][j]);
  cout << res << endl;
}

```