#ifdef INCLUDED_MAIN

// const ll ansmod = 998244353;
// const ll ansmod = 1000000007;

// [lidx, ridx)の区間の文字列を取得 substr("0123456789", 2, 6) -> "2345"
// 第3引数は文字数ではない
string substr(const string &s, ll lidx, ll ridx) {
    if (ridx <= lidx) return "";
    return s.substr(lidx, ridx - lidx);
}

auto solve() {
    GETSTR(S);
    string T = S;
    REV(T);
    if (S == T) return len(S);
    ll N = len(S);
    vector<vector<int>> memo(N + 10, vector<int>(N + 10, -1));
    vector<vector<int>> memo2(N + 10, vector<int>(N + 10, -1));
    auto ff = [&](auto &&f, ll n, ll idx) {
        if (len(S) < n + idx) return false;
        if (memo2[n][idx] != -1) return memo2[n][idx] == 1;
        rep(i, n, len(S)) {
            if (memo[idx][i] == 0) continue;
            if (len(S) < idx + i) break;
            if (memo[idx][i] == 1 && memo2[n][idx + i] != -1) return memo2[n][idx + i] == 1;
            bool isPalindrome = true;
            if (memo[idx][i] == -1) {
                rep(j, i / 2) {
                    if (S[idx + j] != S[idx + i - j - 1]) {
                        isPalindrome = false;
                        break;
                    }
                }
                memo[idx][i] = isPalindrome;
            }
            if (!isPalindrome) continue;
            if (memo2[n][idx + i] == -1) {
                if (len(S) != idx + i) isPalindrome = f(f, n, idx + i);
                memo2[n][idx + i] = isPalindrome;
            } else {
                isPalindrome = memo2[n][idx + i];
            }
            if (isPalindrome) return true;
        }
        memo2[n][idx] = false;
        return false;
    };
    rrepd(n, len(S)) {
        if (n == 1) break;
        if (ff(ff, n, 0)) return n;
    }
    return _1;
}

int main() {
    auto ans = solve();
    // auto ans = (ansmod + (solve() % ansmod)) % ansmod;
    print(ans);
}

// ラムダ再帰
// auto ff = [&](auto &&f, ll x) {};
// ff(ff, 0);

// 以下は動作確認未実施
#else
#define INCLUDED_MAIN

#ifdef LOCAL
#include "../mytemplate.hpp"
#else
#include <algorithm>
#include <bits/extc++.h>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cstddef>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string_view>
#include <type_traits>
#include <utility>
#include <regex>
#endif
using namespace std;
// clang-format off
/* accelration */
// 高速バイナリ生成
#ifndef LOCAL
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

// unordered_mapでpair, vector, tupleをkeyにするためのコード
// (参考文献) https://qiita.com/hamamu/items/4d081751b69aa3bb3557
template<class T> size_t HashCombine(const size_t seed,const T &v){
    return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2));
}
/* pair用 */
template<class T,class S> struct std::hash<std::pair<T,S>>{
    size_t operator()(const std::pair<T,S> &keyval) const noexcept {
        return HashCombine(std::hash<T>()(keyval.first), keyval.second);
    }
};
/* vector用 */
template<class T> struct std::hash<std::vector<T>>{
    size_t operator()(const std::vector<T> &keyval) const noexcept {
        size_t s=0;
        for (auto&& v: keyval) s=HashCombine(s,v);
        return s;
    }
};
/* deque用 */
template<class T> struct std::hash<std::deque<T>>{
    size_t operator()(const std::deque<T> &keyval) const noexcept {
        size_t s=0;
        for (auto&& v: keyval) s=HashCombine(s,v);
        return s;
    }
};
/* tuple用 */
template<int N> struct HashTupleCore{
    template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{
        size_t s=HashTupleCore<N-1>()(keyval);
        return HashCombine(s,std::get<N-1>(keyval));
    }
};
template <> struct HashTupleCore<0>{
    template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{ return 0; }
};
template<class... Args> struct std::hash<std::tuple<Args...>>{
    size_t operator()(const tuple<Args...> &keyval) const noexcept {
        return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval);
    }
};

/* alias */
using ull = __uint128_t;
// using ll = long long; // __int128でTLEするときに切り替える。
using ll = __int128;
using ld = long double;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<ll>;
using vd = vector<ld>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using vvs = vector<vs>;
using vvvs = vector<vvs>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using umpll = unordered_map<ll, ll>;
using umpsl = unordered_map<string, ll>;
using mpll = map<ll, ll>;
using sll = set<ll>;
using msll = multiset<ll>;
using heapqll = priority_queue<ll, vll, greater<ll>>;
using heapqllrev = priority_queue<ll>;
using dll = deque<ll>;

/* REP macro */
#define _overload4(_1,_2,_3,_4,name,...) name
#define _rep(i,n) reps(i,0,n)
#define reps(i,a,n) for (ll i = (a); i < (ll)(n); ++i)
#define repsp(i,a,n,s) for (ll i = (a); i < (ll)(n); i += s)
#define rep(...) _overload4(__VA_ARGS__,repsp, reps,_rep,)(__VA_ARGS__)

#define rrep(i, n) reps(i, 1, n + 1)
#define repd(i,n) for(ll i=n-1;i>=0;i--)
#define rrepd(i,n) for(ll i=n;i>=1;i--)
#define repdict(key, value, dict) for (const auto& [key, value] : dict)
#define repset(x, st) for(auto x : st)

/* define short */
#define endl "\n"
#define pf emplace_front
#define pb emplace_back
#define popleft pop_front
#define popright pop_back
#define mp make_pair
#define ump unordered_map
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define len(x) (ll)(x.size())
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define ARGMAX(x) distance(x.begin(), max_element(all(x)))
#define ARGMIN(x) distance(x.begin(), min_element(all(x)))
#define CLAMP(L, X, R) min(max(L, X), R)
#define IN(L, X, R) (L <= X && X <= R)
#define SET(x) sll(all(x))
#define VEC(x) vll(all(x))
#define GET(x) ll x = in_ll();
#define GET2(x, y) ll x, y; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1];}
#define GET3(x, y, z) ll x, y, z; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1]; z = _A_[2];}
#define GET4(x, y, z, a) ll x, y, z, a; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3];}
#define GET5(x, y, z, a, b) ll x, y, z, a, b; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3]; b = _A_[4];}
#define GET6(x, y, z, a, b, c) ll x, y, z, a, b, c; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3]; b = _A_[4]; c = _A_[5];}
#define GETVLL(x) vll x = in_lls();
#define GETVVLL(x, N) vvll x; rep(i, N) {GETVLL(ab); x.pb(ab);}
#define GETD(x) ld x = in_d();
#define GET2D(x, y) ld x, y; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1];}
#define GET3D(x, y, z) ld x, y, z; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1]; z = _A_[2];}
#define GET4D(x, y, z, a) ld x, y, z, a; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3];}
#define GET5D(x, y, z, a, b) ld x, y, z, a, b; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3]; b = _A_[4];}
#define GET6D(x, y, z, a, b, c) ld x, y, z, a, b, c; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3]; b = _A_[4]; c = _A_[5];}
#define GETVD(x) vd x = in_ds();
#define GETVVD(x, N) vvd x; rep(i, N) {GETVD(ab); x.pb(ab);}
#define GETSTR(x) string x = in_str();
#define GETSTRS(x) vs x; x = in_strs();
#define GETVVS(x, N) vvs x; rep(i, N) x.pb(in_strs());
#define GETVSTR(x, N) vs x; rep(i, N) x.pb(in_str());
#define INI(x, vec) auto x = vec[0];
#define INI2(x, y, vec) auto x = vec[0], y = vec[1];
#define INI3(x, y, z, vec) auto x = vec[0], y = vec[1], z = vec[2];
#define INI4(x, y, z, a, vec) auto x = vec[0], y = vec[1], z = vec[2], a = vec[3];
#define INI5(x, y, z, a, b, vec) auto x = vec[0], y = vec[1], z = vec[2], a = vec[3], b = vec[4];
#define INI6(x, y, z, a, b, c, vec) auto x = vec[0], y = vec[1], z = vec[2], a = vec[3], b = vec[4], c = vec[5];
#define SETPERM(x, N) vll x(N); iota(all(x), 0);
#define SETPERMS(x, s, N) vll x(N); iota(all(x), s);
#define UNUSED(x) ((void)x);
#define printF(x) print(x); cout << flush;
// [INT|LLONG|DBL|LDBL]_[MAX|MIN] 最大最小表現

// 型変換
#define CHARSTR(x) (""s + x)
#define STRBIN2LL(x) std::stoull(x, nullptr, 2)
#define STRLL(x) parse(x)
#define STRD(x) std::stod(x)
#define CHARLL(x) std::stoll(CHARSTR(x))

/* sort */
#define SORT(x) stable_sort(all(x))
#define RSORT(x) stable_sort(rall(x))
#define SORT_IDX(x, idx) stable_sort(all(x), [&](const vll &_a_, const vll &_b_){return _a_[idx] < _b_[idx];})
#define RSORT_IDX(x, idx) stable_sort(all(x), [&](const vll &_a_, const vll &_b_){return _a_[idx] > _b_[idx];})
#define LB_IDX_VEC(c, x) distance((c).begin(), lower_bound(all(c), x)) // O(log N) x未満の最大値についてその右側のidxが求まる
#define UB_IDX_VEC(c, x) distance((c).begin(), upper_bound(all(c), x)) // O(log N) x以上の最小値についてその右側のidxが求まる
#define LB_ITR_VEC(c, x) lower_bound(all(c), x)
#define UB_ITR_VEC(c, x) upper_bound(all(c), x)
// #define LB_IDX_SET(c, x) distance((c).begin(), c.lower_bound(x)) // O(N)
// #define UB_IDX_SET(c, x) distance((c).begin(), c.upper_bound(x)) // O(N)
#define LB_ITR_SET(c, x) c.lower_bound(x)
#define UB_ITR_SET(c, x) c.upper_bound(x)
#define LB_ITR_MAP(c, x) c.lower_bound(x)
#define UB_ITR_MAP(c, x) c.upper_bound(x)
#define KEY_CHANGE(c, k1, k2) { auto i_ = c.extract(k1); i_.key() = k2; c.insert(std::move(i_));}
#define EXIST(key, dict) (dict.find(key) != dict.end())
#define REV(x) reverse(all(x))

namespace // 直値のデフォルトの型をllに。
{
    ll _0 = 0;
    ll _1 = 1;
    ll _2 = 2;
    ll _3 = 3;
    ll _4 = 4;
    ll _5 = 5;
    ll _6 = 6;
    ll _7 = 7;
    ll _8 = 8;
    ll _9 = 9;
    ll _10 = 10;
    ll _11 = 11;
    ll _12 = 12;
    ll _13 = 13;
    ll _14 = 14;
    ll _15 = 15;
    ll _16 = 16;
    ll _17 = 17;
    ll _30 = 30;
    ll _31 = 31;
    ll _32 = 32;
    ll _33 = 33;
    ll _63 = 63;
    ll _64 = 64;
    ll _65 = 65;
    ll _66 = 66;
    ll _126 = 126;
    ll _127 = 127;
    ll _128 = 128;
    ll _129 = 129;
};

void ignore_warning() // ワーニング対策
{
    _0 = _0;
    _1 = _1;
    _2 = _2;
    _3 = _3;
    _4 = _4;
    _5 = _5;
    _6 = _6;
    _7 = _7;
    _8 = _8;
    _9 = _9;
    _10 = _10;
    _11 = _11;
    _12 = _12;
    _13 = _13;
    _14 = _14;
    _15 = _15;
    _16 = _16;
    _17 = _17;
    _30 = _30;
    _31 = _31;
    _32 = _32;
    _33 = _33;
    _63 = _63;
    _64 = _64;
    _65 = _65;
    _66 = _66;
    _126 = _126;
    _127 = _127;
    _128 = _128;
    _129 = _129;
}

/* helper func */
std::ostream &operator<<(std::ostream &dest, __int128 value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}

ll parse(string &s) {
  ll ret = 0;
  bool isplus = true;
  for (ll i = 0; i < s.length(); i++)
    if ('0' <= s[i] && s[i] <= '9')
      ret = 10 * ret + s[i] - '0';
    else if (s[i] == '-')
      isplus ^= isplus;
  return isplus ? ret : -ret;
}

string STR(const vector<char> &cs) {
    return string(cs.begin(), cs.end());
}

string RSTR(const vector<char> &cs) {
    return string(cs.rbegin(), cs.rend());
}

template <typename T>
string STR(T v) {
    ostringstream ss;
    ss << v;
    return ss.str();
}

ll SUM(const vll &v) {
    ll total = 0;
    rep(i, len(v)) {
        total += v[i];
    }
    return total;
}

template<class... T>
constexpr auto min(T... a){
    return min(initializer_list<common_type_t<T...>>{a...});
}

template<class... T>
constexpr auto max(T... a){
    return max(initializer_list<common_type_t<T...>>{a...});
}

// search_length: 走査するベクトル長の上限(先頭から何要素目までを検索対象とするか、1始まりで)
template <typename T> inline bool vector_finder(std::vector<T> vec, T element, unsigned int search_length) {
    auto itr = std::find(vec.begin(), vec.end(), element);
    size_t index = std::distance( vec.begin(), itr );
    if (index == vec.size() || index >= search_length) {return false;} else {return true;}
}
inline void print(const sll& v, string s = " ")
    {bool first = true; for(auto &p : v) { if(first) {first = false; cout << p;} else cout << s << p;} cout << endl;}
inline void print(const msll& v, string s = " ")
    {bool first = true; for(auto &p : v) { if(first) {first = false; cout << p;} else cout << s << p;} cout << endl;}
template <typename T> inline void print(const vector<T>& v, string s = " ")
    {rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
inline void print(const vvll& v, string s = " ")
    {rep(i, len(v)) print(v[i], s);}
template <typename T, typename S> inline void print(const pair<T, S>& p)
    {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << endl;}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v)
    {for (auto&& p : v) print(p);}
template <typename T, typename S> inline void print(const unordered_map<T, S>& d)
    {for (const auto& [key, value] : d) {cout << key << " "; print(value);}}
template <typename T, typename S> inline void print(const map<T, S>& d)
    {for (const auto& [key, value] : d) {cout << key << " "; print(value);}}
inline void print(const vc &d) {rep(i, len(d)) cout << d[i]; cout << endl;}
// 第一引数と第二引数を比較し、第一引数(a)をより大きい/小さい値に上書き
template <typename T> inline bool chmin(T& a, const T& b) {bool compare = a > b; if (a > b) a = b; return compare;}
template <typename T> inline bool chmax(T& a, const T& b) {bool compare = a < b; if (a < b) a = b; return compare;}

/* func */
inline ll in_ll() {string s; getline(cin, s); return STRLL(s);}
inline ld in_d() {string s; getline(cin, s); return STRD(s);}
inline string in_str() {string s; getline(cin, s); return s;}

inline string YESNO(bool cond) {return cond ? "YES" : "NO";}
inline string yesno(bool cond) {return cond ? "yes" : "no";}
inline string YesNo(bool cond) {return cond ? "Yes" : "No";}

/* debug */
namespace debug_print_func {
    std::ostream& os = std::cerr;

    template <class Tp> auto has_cbegin(int)     -> decltype(std::cbegin(std::declval<Tp>()), std::true_type {});
    template <class Tp> auto has_cbegin(...)     -> std::false_type;
    template <class Tp> auto has_value_type(int) -> decltype(std::declval<typename Tp::value_type>(), std::true_type {});
    template <class Tp> auto has_value_type(...) -> std::false_type;

    template <class Tp>[[maybe_unused]] constexpr bool is_iteratable_container_v = decltype(has_cbegin<Tp>(int {}))::value;
    template <class Tp>[[maybe_unused]] constexpr bool is_container_v            = decltype(has_value_type<Tp>(int {}))::value
                                                                                    || is_iteratable_container_v<Tp>;

    template <>        [[maybe_unused]] constexpr bool is_iteratable_container_v<std::string_view> = false;
    template <>        [[maybe_unused]] constexpr bool is_container_v<std::string_view>            = false;
    #if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING)
    template <>        [[maybe_unused]] constexpr bool is_iteratable_container_v<std::string>      = false;
    template <>        [[maybe_unused]] constexpr bool is_container_v<std::string>                 = false;
    #endif

    template <class Tp, class... Ts> struct first_element { using type = Tp; };
    template <class... Ts> using first_t = typename first_element<Ts...>::type;

    template <class Tp, std::enable_if_t<!decltype(has_value_type<Tp>(int {}))::value, std::nullptr_t> = nullptr>
        auto check_elem(int) -> decltype(*std::cbegin(std::declval<Tp>()));
    template <class Tp, std::enable_if_t<decltype(has_value_type<Tp>(int {}))::value, std::nullptr_t> = nullptr>
        auto check_elem(int) -> typename Tp::value_type;
    template <class Tp>
        auto check_elem(...) -> void;

    template <class Tp> using elem_t = decltype(check_elem<Tp>(int {}));

    template <class Tp> [[maybe_unused]] constexpr bool is_multidim_container_v = is_container_v<Tp>
                                                                                    && is_container_v<elem_t<Tp>>;

    template <class Tp> std::enable_if_t<!is_container_v<Tp>> out(const Tp&);
    void out(const char&);
    void out(const char*);
    void out(const std::string_view&);

    #if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING)
    void out(const std::string&);
    #endif

    #ifdef __SIZEOF_INT128__
    void out(const __int128&);
    void out(const unsigned __int128&);
    #endif

    template <class Tp1, class Tp2> void out(const std::pair<Tp1, Tp2>&);

    #if (defined _GLIBCXX_TUPLE) || (defined _LIBCPP_TUPLE)
    template <class... Ts> void out(const std::tuple<Ts...>&);
    #endif

    #if (defined _GLIBCXX_STACK) || (defined _LIBCPP_STACK)
    template <class... Ts> void out(std::stack<Ts...>);
    #endif

    #if (defined _GLIBCXX_QUEUE) || (defined _LIBCPP_QUEUE)
    template <class... Ts> void out(std::queue<Ts...>);
    template <class... Ts> void out(std::priority_queue<Ts...>);
    #endif

    template <class C>
    std::enable_if_t<is_iteratable_container_v<C>> out(const C&);

    template <class Tp> std::enable_if_t<!is_container_v<Tp>> out(const Tp& arg) {
        os << arg;
    }

    void out(const char& arg) {
        os << '\'' << arg << '\'';
    }

    void out(const char* arg) {
        os << '\"' << arg << '\"';
    }

    void out(const ld arg) {
        if (arg == LDBL_MAX) {
            os << "∞";
        } else if (arg == -LDBL_MAX) {
            os << "-∞";
        } else {
            os << arg;
        }
    }

    void out(const std::string_view& arg) {
        os << '\"' << arg << '\"';
    }

    #if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING)
    void out(const std::string& arg) {
        os << '\"' << arg << '\"';
    }
    #endif

    #ifdef __SIZEOF_INT128__
    void out(const __int128& arg) {
        if (arg == ULLONG_MAX) {
            os << "∞";
        } else {
            int sign = (arg < 0) ? (-1) : 1;
            if (sign == -1) os << '-';
            __int128 base = sign;
            while (sign * arg >= sign * base * 10) base *= 10;
            while (base) {
                os << static_cast<char>('0' + (arg / base % 10));
                base /= 10;
            }
        }
    }

    void out(const unsigned __int128& arg) {
        if (arg == ULLONG_MAX) {
            os << "∞";
        } else {
            unsigned __int128 base = 1;
            while (arg >= base * 10) base *= 10;
            while (base) {
                os << static_cast<char>('0' + (arg / base % 10));
                base /= 10;
            }
        }
    }
    #endif

    template <class Tp1, class Tp2> void out(const std::pair<Tp1, Tp2>& arg) {
        os << '(';
        out(arg.first);
        os << ", ";
        out(arg.second);
        os << ')';
    }

    #if (defined _GLIBCXX_TUPLE) || (defined _LIBCPP_TUPLE)
    template <class T, std::size_t... Is> void print_tuple(const T& arg, std::index_sequence<Is...>) {
        static_cast<void>(((os << (Is == 0 ? "" : ", "), out(std::get<Is>(arg))), ...));
    }

    template <class... Ts> void out(const std::tuple<Ts...>& arg) {
        os << '(';
        print_tuple(arg, std::make_index_sequence<sizeof...(Ts)>());
        os << ')';
    }
    #endif

    #if (defined _GLIBCXX_STACK) || (defined _LIBCPP_STACK)
    template <class... Ts> void out(std::stack<Ts...> arg) {
        if (arg.empty()) {
        os << "<empty stack>";
        return;
        }
        os << "[ ";
        while (!arg.empty()) {
        out(arg.top());
        os << ' ';
        arg.pop();
        }
        os << ']';
    }
    #endif

    #if (defined _GLIBCXX_QUEUE) || (defined _LIBCPP_QUEUE)
    template <class... Ts> void out(std::queue<Ts...> arg) {
        if (arg.empty()) {
        os << "<empty queue>";
        return;
        }
        os << "[ ";
        while (!arg.empty()) {
        out(arg.front());
        os << ' ';
        arg.pop();
        }
        os << ']';
    }
    template <class... Ts> void out(std::priority_queue<Ts...> arg) {
        if (arg.empty()) {
        os << "<empty priority_queue>";
        return;
        }
        os << "[ ";
        while (!arg.empty()) {
        out(arg.top());
        os << ' ';
        arg.pop();
        }
        os << ']';
    }
    #endif

    template <class Container>
    std::enable_if_t<is_iteratable_container_v<Container>> out(const Container& arg) {
        if (std::distance(std::cbegin(arg), std::cend(arg)) == 0) {
        os << "<empty container>";
        return;
        }
        os << "[ ";
        std::for_each(std::cbegin(arg), std::cend(arg), [](const elem_t<Container>& elem) {
        out(elem);
        os << ' ';
        });
        os << ']';
    }

    template <class Tp> std::enable_if_t<!is_multidim_container_v<Tp>>
    print(std::string_view name, const Tp& arg) {
        os << name << ": ";
        out(arg);
        if constexpr (is_container_v<Tp>)
        os << '\n';
    }

    template <class Tp> std::enable_if_t<is_multidim_container_v<Tp>>
    print(std::string_view name, const Tp& arg) {
        os << name << ": ";
        if (std::distance(std::cbegin(arg), std::cend(arg)) == 0) {
        os << "<empty multidimensional container>\n";
        return;
        }
        std::for_each(std::cbegin(arg), std::cend(arg),
        [&name, is_first_elem = true](const elem_t<Tp>& elem) mutable {
            if (is_first_elem)
            is_first_elem = false;
            else
            for (std::size_t i = 0; i < name.length() + 2; i++)
                os << ' ';
            out(elem);
            os << '\n';
        });
    }

    template <class Tp, class... Ts> void multi_print(std::string_view names, const Tp& arg, const Ts&... args) {
        if constexpr (sizeof...(Ts) == 0) {
        names.remove_suffix(
            std::distance(
            names.crbegin(),
            std::find_if_not(names.crbegin(), names.crend(),
                            [](const char c) { return std::isspace(c); })
            )
        );
        print(names, arg);
        if constexpr (!is_container_v<Tp>)
            os << '\n';
        } else {
        std::size_t comma_pos = 0;

        for (std::size_t i = 0, paren_depth = 0, inside_quote = false; i < names.length(); i++) {
            if (!inside_quote && paren_depth == 0 && i > 0 && names[i - 1] != '\'' && names[i] == ',') {
            comma_pos = i;
            break;
            }
            if (names[i] == '\"') {
            if (i > 0 && names[i - 1] == '\\') continue;
            inside_quote ^= true;
            }
            if (!inside_quote && names[i] == '(' && (i == 0 || names[i - 1] != '\''))
            paren_depth++;
            if (!inside_quote && names[i] == ')' && (i == 0 || names[i - 1] != '\''))
            paren_depth--;
        }

        const std::size_t first_varname_length = comma_pos - std::distance(
            names.crend() - comma_pos,
            std::find_if_not(
            names.crend() - comma_pos, names.crend(),
            [](const char c) { return std::isspace(c); }
            )
        );
        print(names.substr(0, first_varname_length), arg);

        if constexpr (!is_container_v<Tp>) {
            if constexpr (is_container_v<first_t<Ts...>>)
            os << '\n';
            else
            os << " | ";
        }

        const std::size_t next_varname_begins_at = std::distance(
            names.cbegin(),
            std::find_if_not(
            names.cbegin() + comma_pos + 1, names.cend(),
            [](const char c) { return std::isspace(c); }
            )
        );
        names.remove_prefix(next_varname_begins_at);

        multi_print(names, args...);
        }
    }
}  // namespace debug_print

#ifdef LOCAL
#  define debug(...) cerr << "\033[33m(line:" << __LINE__ << ") " << endl; debug_print_func::multi_print(#__VA_ARGS__, __VA_ARGS__); cerr << "\033[m";
#else
#  define debug(...) ;
#endif

/* 標準入力 */
vs in_strs(const string &delimiter = " ")
{
    string s;
    getline(cin, s);

    vs output;
    bitset<255> delims;
    for (unsigned char c: delimiter)
    {
        delims[c] = true;
    }
    string::const_iterator beg;
    bool in_token = false;
    for( string::const_iterator it = s.cbegin(), end = s.cend(); it != end; ++it )
    {
    if( delims[*it] )
    {
    if( in_token )
    {
        output.pb(beg, it);
        in_token = false;
    }
    }
    else if( !in_token )
    {
        beg = it;
        in_token = true;
    }
    }
    if( in_token )
        output.pb(beg, s.cend());
    return output;
}

inline vll in_lls()
{
    vll vals;
    vs tokens = in_strs();
    for (string i: tokens) vals.pb(STRLL(i));
    return vals;
}

inline vd in_ds()
{
    vd vals;
    vs tokens = in_strs();
    for (string i: tokens) vals.pb(STRD(i));
    return vals;
}

inline vvll in_llss(ll line) // 複数行文字列解析
{
    vvll valss;
    rep(i, line) valss.pb(in_lls());
    return valss;
}

inline vs in_vs(ll line) // 複数行文字列解析
{
    vs vecs;
    rep(i, line) {
        vecs.pb(in_str());
    }
    return vecs;
}

inline ll popcnt(ll x) { return __builtin_popcountll(x); }

template <typename T, typename U>
T ceil(T x, U y) {
  return (x > 0 ? (x + y - 1) / y : x / y);
}

template <typename T, typename U>
T floor(T x, U y) {
  return (x > 0 ? x / y : (x - y + 1) / y);
}

template <typename T>
class Counter
{
public:
    unordered_map<T, ll> tbl_;
    ll max_cnt_ = 0;
    T max_key_;
    ll min_cnt_ = -1;
    T min_key_;

    Counter(const vector<T> &vec) {
        rep(i, len(vec)) {
            ll v = ++tbl_[vec[i]];
            if (max_cnt_ < v) {
                max_cnt_ = v;
                max_key_ = vec[i];
            }
        }
    }

    ll count(T key) {
        return tbl_[key];
    }

    T maxkey() {
        return max_key_;
    }

    ll maxcnt() {
        return max_cnt_;
    }

    T minkey() {
        if (min_cnt_ == -1) {
            mincnt();
        }
        return min_key_;
    }

    ll mincnt() {
        if (min_cnt_ == -1) {
            min_key_ = tbl_.begin()->first;
            min_cnt_ = tbl_.begin()->second;
            for(auto itr = tbl_.begin(); itr != tbl_.end(); itr++){
                if(min_cnt_ > itr->second) {
                    min_key_ = itr->first;
                    min_cnt_ = itr->second;
                }
            }
        }
        return min_cnt_;
    }
};

template <typename T>
vector<T> accsum(const vector<T> &vec, ll ansmod = 0) {
    if (len(vec) == 0) return vector<T>();
    vector<T> acc = {0};
    if (ansmod != 0) {
        rep (i, len(vec)) acc.pb((acc[i] + vec[i]) % ansmod);
    } else {
        rep (i, len(vec)) acc.pb(acc[i] + vec[i]);
    }
    return acc;
}

template <typename T>
vector<T> accmax(const vector<T> &vec) {
    if (len(vec) == 0) return vector<T>();
    vector<T> acc = {vec[0]};
    reps (i, 1, len(vec)) acc.pb(max(acc[i - 1], vec[i]));
    return acc;
}

template <typename T>
vector<T> accmin(const vector<T> &vec) {
    if (len(vec) == 0) return vector<T>();
    vector<T> acc = {vec[0]};
    reps (i, 1, len(vec)) acc.pb(min(acc[i - 1], vec[i]));
    return acc;
}

// https://howardhinnant.github.io/combinations.html
namespace howardhinnantdetail
{

// Rotates two discontinuous ranges to put *first2 where *first1 is.
//     If last1 == first2 this would be equivalent to rotate(first1, first2, last2),
//     but instead the rotate "jumps" over the discontinuity [last1, first2) -
//     which need not be a valid range.
//     In order to make it faster, the length of [first1, last1) is passed in as d1,
//     and d2 must be the length of [first2, last2).
//  In a perfect world the d1 > d2 case would have used swap_ranges and
//     reverse_iterator, but reverse_iterator is too inefficient.
template <class BidirIter>
void
rotate_discontinuous(BidirIter first1, BidirIter last1,
                     typename std::iterator_traits<BidirIter>::difference_type d1,
                     BidirIter first2, BidirIter last2,
                     typename std::iterator_traits<BidirIter>::difference_type d2)
{
    using std::swap;
    if (d1 <= d2)
        std::rotate(first2, std::swap_ranges(first1, last1, first2), last2);
    else
    {
        BidirIter i1 = last1;
        while (first2 != last2)
            swap(*--i1, *--last2);
        std::rotate(first1, i1, last1);
    }
}

// Rotates the three discontinuous ranges to put *first2 where *first1 is.
// Just like rotate_discontinuous, except the second range is now represented by
//    two discontinuous ranges: [first2, last2) + [first3, last3).
template <class BidirIter>
void
rotate_discontinuous3(BidirIter first1, BidirIter last1,
                      typename std::iterator_traits<BidirIter>::difference_type d1,
                      BidirIter first2, BidirIter last2,
                      typename std::iterator_traits<BidirIter>::difference_type d2,
                      BidirIter first3, BidirIter last3,
                      typename std::iterator_traits<BidirIter>::difference_type d3)
{
    rotate_discontinuous(first1, last1, d1, first2, last2, d2);
    if (d1 <= d2)
        rotate_discontinuous(std::next(first2, d2 - d1), last2, d1, first3, last3, d3);
    else
    {
        rotate_discontinuous(std::next(first1, d2), last1, d1 - d2, first3, last3, d3);
        rotate_discontinuous(first2, last2, d2, first3, last3, d3);
    }
}

// Call f() for each combination of the elements [first1, last1) + [first2, last2)
//    swapped/rotated into the range [first1, last1).  As long as f() returns
//    false, continue for every combination and then return [first1, last1) and
//    [first2, last2) to their original state.  If f() returns true, return
//    immediately.
//  Does the absolute mininum amount of swapping to accomplish its task.
//  If f() always returns false it will be called (d1+d2)!/(d1!*d2!) times.
template <class BidirIter, class Function>
bool
combine_discontinuous(BidirIter first1, BidirIter last1,
                      typename std::iterator_traits<BidirIter>::difference_type d1,
                      BidirIter first2, BidirIter last2,
                      typename std::iterator_traits<BidirIter>::difference_type d2,
                      Function& f,
                      typename std::iterator_traits<BidirIter>::difference_type d = 0)
{
    typedef typename std::iterator_traits<BidirIter>::difference_type D;
    using std::swap;
    if (d1 == 0 || d2 == 0)
        return f();
    if (d1 == 1)
    {
        for (BidirIter i2 = first2; i2 != last2; ++i2)
        {
            if (f())
                return true;
            swap(*first1, *i2);
        }
    }
    else
    {
        BidirIter f1p = std::next(first1);
        BidirIter i2 = first2;
        for (D d22 = d2; i2 != last2; ++i2, --d22)
        {
            if (combine_discontinuous(f1p, last1, d1-1, i2, last2, d22, f, d+1))
                return true;
            swap(*first1, *i2);
        }
    }
    if (f())
        return true;
    if (d != 0)
        rotate_discontinuous(first1, last1, d1, std::next(first2), last2, d2-1);
    else
        rotate_discontinuous(first1, last1, d1, first2, last2, d2);
    return false;
}

// A binder for binding arguments to call combine_discontinuous
template <class Function, class BidirIter>
class call_combine_discontinuous
{
    typedef typename std::iterator_traits<BidirIter>::difference_type D;
    Function f_;
    BidirIter first1_;
    BidirIter last1_;
    D d1_;
    BidirIter first2_;
    BidirIter last2_;
    D d2_;

public:
    call_combine_discontinuous(
                      BidirIter first1, BidirIter last1,
                      D d1,
                      BidirIter first2, BidirIter last2,
                      D d2,
                      Function& f)
        : f_(f), first1_(first1), last1_(last1), d1_(d1),
                 first2_(first2), last2_(last2), d2_(d2) {}

    bool operator()()
    {
        return combine_discontinuous(first1_, last1_, d1_, first2_, last2_, d2_, f_);
    }
};

// See combine_discontinuous3
template <class BidirIter, class Function>
bool
combine_discontinuous3_(BidirIter first1, BidirIter last1,
                        typename std::iterator_traits<BidirIter>::difference_type d1,
                        BidirIter first2, BidirIter last2,
                        typename std::iterator_traits<BidirIter>::difference_type d2,
                        BidirIter first3, BidirIter last3,
                        typename std::iterator_traits<BidirIter>::difference_type d3,
                        Function& f,
                        typename std::iterator_traits<BidirIter>::difference_type d = 0)
{
    typedef typename std::iterator_traits<BidirIter>::difference_type D;
    using std::swap;
    if (d1 == 1)
    {
        for (BidirIter i2 = first2; i2 != last2; ++i2)
        {
            if (f())
                return true;
            swap(*first1, *i2);
        }
        if (f())
            return true;
        swap(*first1, *std::prev(last2));
        swap(*first1, *first3);
        for (BidirIter i2 = std::next(first3); i2 != last3; ++i2)
        {
            if (f())
                return true;
            swap(*first1, *i2);
        }
    }
    else
    {
        BidirIter f1p = std::next(first1);
        BidirIter i2 = first2;
        for (D d22 = d2; i2 != last2; ++i2, --d22)
        {
            if (combine_discontinuous3_(f1p, last1, d1-1, i2, last2, d22, first3,
                                        last3, d3, f, d+1))
                return true;
            swap(*first1, *i2);
        }
        i2 = first3;
        for (D d22 = d3; i2 != last3; ++i2, --d22)
        {
            if (combine_discontinuous(f1p, last1, d1-1, i2, last3, d22, f, d+1))
                return true;
            swap(*first1, *i2);
        }
    }
    if (f())
        return true;
    if (d1 == 1)
        swap(*std::prev(last2), *first3);
    if (d != 0)
    {
        if (d2 > 1)
            rotate_discontinuous3(first1, last1, d1, std::next(first2), last2, d2-1, first3, last3, d3);
        else
            rotate_discontinuous(first1, last1, d1, first3, last3, d3);
    }
    else
        rotate_discontinuous3(first1, last1, d1, first2, last2, d2, first3, last3, d3);
    return false;
}

// Like combine_discontinuous, but swaps/rotates each combination out of
//    [first1, last1) + [first2, last2) + [first3, last3) into [first1, last1).
//    If f() always returns false, it is called (d1+d2+d3)!/(d1!*(d2+d3)!) times.
template <class BidirIter, class Function>
bool
combine_discontinuous3(BidirIter first1, BidirIter last1,
                       typename std::iterator_traits<BidirIter>::difference_type d1,
                       BidirIter first2, BidirIter last2,
                       typename std::iterator_traits<BidirIter>::difference_type d2,
                       BidirIter first3, BidirIter last3,
                       typename std::iterator_traits<BidirIter>::difference_type d3,
                       Function& f)
{
    typedef call_combine_discontinuous<Function&, BidirIter> F;
    F fbc(first2, last2, d2, first3, last3, d3, f);  // BC
    return combine_discontinuous3_(first1, last1, d1, first2, last2, d2, first3, last3, d3, fbc);
}

// See permute
template <class BidirIter, class Function>
bool
permute_(BidirIter first1, BidirIter last1,
         typename std::iterator_traits<BidirIter>::difference_type d1,
         Function& f)
{
    using std::swap;
    switch (d1)
    {
    case 0:
    case 1:
        return f();
    case 2:
        if (f())
            return true;
        swap(*first1, *std::next(first1));
        return f();
    case 3:
        {
        if (f())
            return true;
        BidirIter f2 = std::next(first1);
        BidirIter f3 = std::next(f2);
        swap(*f2, *f3);
        if (f())
            return true;
        swap(*first1, *f3);
        swap(*f2, *f3);
        if (f())
            return true;
        swap(*f2, *f3);
        if (f())
            return true;
        swap(*first1, *f2);
        swap(*f2, *f3);
        if (f())
            return true;
        swap(*f2, *f3);
        return f();
        }
    }
    BidirIter fp1 = std::next(first1);
    for (BidirIter p = fp1; p != last1; ++p)
    {
        if (permute_(fp1, last1, d1-1, f))
            return true;
        std::reverse(fp1, last1);
        swap(*first1, *p);
    }
    return permute_(fp1, last1, d1-1, f);
}

// Calls f() for each permutation of [first1, last1)
// Divided into permute and permute_ in a (perhaps futile) attempt to
//    squeeze a little more performance out of it.
template <class BidirIter, class Function>
bool
permute(BidirIter first1, BidirIter last1,
        typename std::iterator_traits<BidirIter>::difference_type d1,
        Function& f)
{
    using std::swap;
    switch (d1)
    {
    case 0:
    case 1:
        return f();
    case 2:
        {
        if (f())
            return true;
        BidirIter i = std::next(first1);
        swap(*first1, *i);
        if (f())
            return true;
        swap(*first1, *i);
        }
        break;
    case 3:
        {
        if (f())
            return true;
        BidirIter f2 = std::next(first1);
        BidirIter f3 = std::next(f2);
        swap(*f2, *f3);
        if (f())
            return true;
        swap(*first1, *f3);
        swap(*f2, *f3);
        if (f())
            return true;
        swap(*f2, *f3);
        if (f())
            return true;
        swap(*first1, *f2);
        swap(*f2, *f3);
        if (f())
            return true;
        swap(*f2, *f3);
        if (f())
            return true;
        swap(*first1, *f3);
        }
        break;
    default:
        BidirIter fp1 = std::next(first1);
        for (BidirIter p = fp1; p != last1; ++p)
        {
            if (permute_(fp1, last1, d1-1, f))
                return true;
            std::reverse(fp1, last1);
            swap(*first1, *p);
        }
        if (permute_(fp1, last1, d1-1, f))
            return true;
        std::reverse(first1, last1);
        break;
    }
    return false;
}

// Creates a functor with no arguments which calls f_(first_, last_).
//   Also has a variant that takes two It and ignores them.
template <class Function, class It>
class bound_range
{
    Function f_;
    It first_;
    It last_;
public:
    bound_range(Function f, It first, It last)
        : f_(f), first_(first), last_(last) {}

    bool
    operator()()
    {
        return f_(first_, last_);
    }

    bool
    operator()(It, It)
    {
        return f_(first_, last_);
    }
};

// A binder for binding arguments to call permute
template <class Function, class It>
class call_permute
{
    typedef typename std::iterator_traits<It>::difference_type D;
    Function f_;
    It first_;
    It last_;
    D d_;
public:
    call_permute(Function f, It first, It last, D d)
        : f_(f), first_(first), last_(last), d_(d) {}

    bool
    operator()()
    {
        return permute(first_, last_, d_, f_);
    }
};

}  // detail

template <class BidirIter, class Function>
Function
for_each_combination(BidirIter first, BidirIter last,
                     BidirIter mid, Function f)
{
    howardhinnantdetail::bound_range<Function&, BidirIter> wfunc(f, first, mid);
    howardhinnantdetail::combine_discontinuous(first, mid, std::distance(first, mid),
                                  mid, last, std::distance(mid, last),
                                  wfunc);
    return f;
}

class BitwiseFullSearch
{
public:
    ll count_;
    std::function<void(const vll &ptn, ll &count)> checkcount_; // カウントするロジックのラムダ式を突っ込む。

    BitwiseFullSearch(std::function<void(const vll &ptn, ll &count)> f) : count_(0), checkcount_(f) {}
    // ここは触らなくてよい(パターンを列挙しているだけ)
    bool operator()(vll::iterator it1, vll::iterator it2)
    {
        vll ptn;
        while (it1 != it2)
        {
            ptn.pb(*it1);
            ++it1;
        }
        checkcount_(ptn, count_);
        return false;
    }
};

ll _comb_ptn_count(ll R, const std::function<void(const vll &ptn, ll &count)> &f, vll &_A_) {
    auto B = BitwiseFullSearch(f);
    vll::iterator _R_ = _A_.begin() + R;
    B = for_each_combination(all(_A_), _R_, B);
    return B.count_;
}

ll comb_ptn_count(ll N, ll R, const std::function<void(const vll &ptn, ll &count)> &f) {
    SETPERM(_A_, N);
    return _comb_ptn_count(R, f, _A_);
}

vvll get_comb_ptn(ll N, ll R) {
    vvll cb;
    auto f = [&](const vll &ptn, ll &count)
    {
        UNUSED(count);
        cb.pb(ptn);
    };
    comb_ptn_count(N, R, f);
    return cb;
}

ll comb_allptn_count(ll N, const std::function<void(const vll &ptn, ll &count)> &f) {
    ll cnt = 0;
    SETPERM(_A_, N);
    rep(r, N + 1) {
        cnt += _comb_ptn_count(r, f, _A_);
    }
    return cnt;
}

// N が 20とかだとSegmentation faultが発生する。スタック領域が足りなくなるか。
vvll get_comb_allptn(ll N) {
    vvll cb;
    auto f = [&](const vll &ptn, ll &count)
    {
        UNUSED(count);
        cb.pb(ptn);
    };
    comb_allptn_count(N, f);
    return cb;
}

vvll get_perm_ptn(ll N) {
    vvll ptn;
    SETPERM(_A_, N);
    do {
        ptn.pb(_A_);
    } while(next_permutation(all(_A_)));
    return ptn;
}

// n個からr個有効にしたbitパターンの数値を列挙
// 下1桁目から0, 1, 2番目が有効無効を表す。(Nは60くらいまで)
vll get_bitptn(ll N, ll R) {
    vll bitptns;
    auto ptns = get_comb_ptn(N, R);
    rep (i, len(ptns)) {
        ll bitptn = 0;
        rep (j, R) {
            bitptn += _1 << ptns[i][j];
        }
        bitptns.pb(bitptn);
    }
    return bitptns;
}

inline ll sumk(ll n)
{
    return n * (n + 1) / 2;
}

inline ll sumk2(ll n)
{
    return n * (n + 1) * (2 * n + 1) / 6;
}

ll POW(ll n, ll r)
{
    if (r == 0) return 1;
    else if (r % 2 == 0) return POW(n * n, (ll)(r / 2));
    else return n * POW(n, r - 1);
}

inline string alpha()
{
    return "abcdefghijklmnopqrstuvwxyz";
}

inline ll alpha_num(char c)
{
    return ll(c) - ll('a');
}

inline string alpha_big()
{
    return "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
}

inline ll alpha_big_num(char c)
{
    return ll(c) - ll('A');
}

inline char alpha_big2small(char C) {
    static string s = alpha();
    ll idx = alpha_big_num(C);
    return IN(0, idx, 25) ? s[idx] : C;
}

inline char alpha_small2big(char c) {
    static string s = alpha_big();
    ll idx = alpha_num(c);
    return IN(0, idx, 25) ? s[idx] : c;
}

string zerofill(ll v, ll outputlen)
{
    string s = STR(v);
    string zerostr(outputlen - len(s), '0');
    return zerostr + s;
}

// ランレングス圧縮
// auto rle = RunLengthEncoding(S);
// rep(i, len(rle)) {
//     auto &[c, cnt] = rle[i];
// }
vector<pair<char, ll>> RunLengthEncoding(const string &s) {
    vector<pair<char, ll>> tbl;
    char c = s[0];
    ll cnt = 1;
    ll N = len(s);
    reps (i, 1, N) {
        if (c == s[i]) {
            cnt++;
        }
        else {
            tbl.pb(mp(c, cnt));
            c = s[i];
            cnt = 1;
        }
    }
    tbl.pb(mp(c, cnt));
    return tbl;
}

// 約数個数列挙(MAXNまで)
vll divisors_count(ll MAXN = 1000000)
{
    vll div = vll(MAXN + 1, 0);
    rrep(n, MAXN) repsp(m, n, MAXN + 1, n) {
        div[m] += 1;
    }
    return div;
}

// Nの階乗がkで何回割れるかを返す。(ルジャンドルの公式)
ll LegendresFormula(ll N, ll k) {
    ll v = k;
    ll cnt = 0;
    while(v <= N) {
        cnt += floor(N, v);
        v *= k;
    }
    return cnt;
}

// 約数列挙
// 約数の個数は大体n^(1/3)個
vll make_divisors(ll n) {
    vll divisors;
    for(ll i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            divisors.pb(i);
            if(i != n / i) {
                divisors.pb(n / i);
            }
        }
    }
    return divisors;
}

// N以下の素数列挙(Nはせいぜい10^7くらいまで)
inline vll eratosthenes(ll N) {
    vll ps;
    vector<bool> primes(N + 1);
    rep(i, len(primes)) primes[i] = true;
    primes[0] = primes[1] = false;
    rep(i, len(primes)) {
        if (primes[i]) {
            ps.pb(i);
            for (ull j = i + i; j < len(primes); j += i) {
                primes[j] = false;
            }
        }
    }
    return ps;
}

// 高速素因数分解(MAXNの範囲まで)
class Prime
{
public:
    static vll sieve; // 何回もPrimeのインスタンスを生成するときはstaticをはずして、下の実体もコメントアウトする。
    Prime(ll MAXN = 10000000) {
        rep(i, MAXN + 1) sieve.pb(i);
        ll p = 2;
        while (p * p <= MAXN) {
            if (sieve[p] == p) {
                repsp(q, 2 * p, MAXN + 1, p) {
                    if (sieve[q] == q) sieve[q] = p;
                }
            }
            p += 1;
        }
    }

    Counter<ll> prime(ll n) {
        if (n == 1) return Counter<ll>(vll());
        vll tmp;
        while (n > 1) {
            tmp.pb(sieve[n]);
            n = (ll)(n / sieve[n]);
        }
        return Counter<ll>(tmp);
    }
};
vll Prime::sieve = vll();


#define mod_m2p(a, m) (((m) + (a)) % (m))
#define mod_add(a, b, m) (((a) + (b)) % (m))
#define mod_sub(a, b, m) (((m) + (a) - (b)) % (m))
#define mod_mul(a, b, m) (mod_m2p(((a) % (m)) * ((b) % (m)), (m)))
ll mod_bipow_(ll x, ll y, ll m) {   // x^y by bisection method
    if (y == 0) return 1 % m;
    else if (y == 1) return x % m;
    else if (y % 2 == 0) {
        ll val = mod_bipow_(x, (ll)(y / 2), m);
        return mod_mul(val, val, m);
    } else {
        ll val = mod_bipow_(x, (ll)(y / 2), m);
        return mod_mul(mod_mul(val, val, m), x, m);
    }
}

ll mod_inv(ll x, ll pm) { return mod_bipow_(mod_m2p(x, pm), pm - 2, pm); }   // x^{-1} = x^{MOD-2} (MOD: prime number)
ll mod_div(ll a, ll b, ll m) { return mod_mul(mod_m2p(a, m), mod_inv(mod_m2p(b, m), m), m); }   // a/b = a*b^{-1}
ll mod_bipow(ll x, ll y, ll m) {
    if (y < 0) {
        ll xx = mod_div((ll)1, x, m);
        return mod_bipow_(xx, -y, m);
    }
    return mod_bipow_(x, y, m);
}

ll mysqrt(ll n) {
    ll ok = 0, ng = n + 1;
    while (ng - ok > 1) {
        ll mid = (ng + ok) >> 1;
        if (mid * mid <= n) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

// nCkをmで割った余りを求める
class Combination {
    const ll n_;
    const ll m_;
    vll facts_;
    vll inv_facts_;
public:
    Combination(ll N, ll mod) : n_(2 * N), m_(mod), facts_(n_ + 1), inv_facts_(n_ + 1) {
        rep(i, n_ + 1) facts_[i] = i == 0 ? 1 : mod_mul(facts_[i - 1], i, m_);
        for (ll i = n_; i >= 0; i--) inv_facts_[i] = i == n_ ? mod_inv(facts_[n_], m_) : mod_mul(inv_facts_[i + 1], i + 1, m_);   // (i!)^{-1}=((i+1)!)^{-1}*(i+1)
    }
    ll nPr(ll n, ll r) {
        if (n < r) return _0;
        return mod_mul(facts_[n], inv_facts_[n - r], m_);
    }
    ll nCr(ll n, ll r) {
        if (n < r) return _0;
        return mod_mul(facts_[n], mod_mul(inv_facts_[r], inv_facts_[n - r], m_), m_);
    }
    ll nHr(ll n, ll r) {
        return nCr(n + r - 1, r);
    }
    ll catalan(ll n) { // https://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0
        return mod_mul(nCr(2 * n, n), mod_inv(n + 1, m_), m_);
    }
    // カタラン数・・・(2n C n)/(n + 1) = (2n C n) - (2n C n-1)
    // c0 = 1, c_n = rep(i, n) c[i] * c[n - i - 1]
    // c0から順に1,1,2,5,14,42,132,429,1430,...

    // 1 <= a1 <= a2 <= a3 <= a4 <= ... <= ak <= Nの組み合わせの数。
    // CombinationのコンストラクタにN + Kを入れておくこと。
    ll loopcnt(ll n, ll k) {
        assert(n + k <= n_);
        return nCr(n - 1 + k, n - 1);
    }
};

// 1-originで扱う。
class UnionFind {
    ll n_;
    vll size_;
    vll par_;
    vll link_;
    vll rank_;
    vll par_diff_;

public:
    UnionFind(ll n) : n_(n + 1), size_(n_, 1), par_(n_), link_(n_), rank_(n_), par_diff_(n_)
    {
        iota(all(par_), 0);
        iota(all(link_), 0);
    }

    ll find(ll x) {
        if (par_[x] == x) return x;
        else {
            ll ret = find(par_[x]);
            if (par_diff_[par_[x]] == LLONG_MAX) par_diff_[x] = LLONG_MAX;
            else par_diff_[x] += par_diff_[par_[x]];
            return par_[x] = ret;
        }
    }

    ll operator[](ll x) { return find(x); }

    bool unite(ll x, ll y, ll w = 0) {
        if (x != 0 && same(x, y) && diff(x, y) != w) unite(0, y);
        ll rx = find(x);
        ll ry = find(y);
        ll wt = w;
        wt += weight(x);
        wt -= weight(y);
        if (rx == ry) {
            return false;
        }
        if (ry < rx) {
            swap(rx, ry);
            wt = -wt;
        }
        size_[rx] += size_[ry];
        if (rank_[rx] == rank_[ry]) rank_[rx]++;

        size_[ry] = 0;
        par_[ry] = rx;
        par_diff_[ry] = wt;
        swap(link_[rx], link_[ry]);
        return true;
    }

    vll find_all() {
        vll A(n_);
        rep(i, n_) A[i] = find(i);
        return A;
    }

    vll members(ll x) {
        vll mems = vll{x};
        for (ll y = link_[x]; y != x; y = link_[y]) mems.pb(y);
        return mems;
    }

    ll size(ll x) {
        return size_[find(x)];
    }

    bool same(ll x, ll y) {
        return find(x) == find(y);
    }

    vll roots() {
        vll rs;
        reps(i, 1, n_) if (size_[i] > 0) rs.pb(i);
        return rs;
    }

    ll group_count() {
        return len(roots());
    }

    unordered_map<ll, vll> all_group_members() {
        unordered_map<ll, vll> group_members;
        reps(member, 1, n_) group_members[find(member)].pb(member);
        return group_members;
    }

    ll weight(ll x) {
        find(x);
        return par_diff_[x];
    }

    ll diff(ll x, ll y) {
        if (same(0, x) || same(0, y)) return LLONG_MAX;
        return weight(y) - weight(x);
    }
};

class Graph
{
private:
    unordered_map<ll, vector<pll>> edges_;
    unordered_map<ll, vector<pll>> ignore_edges_; // 多重辺で同じ重みの辺があるとダメ
    vll outdeg_;
    vll indeg_;

    const ll V_;
    const bool dir_;
    const ll ansmod_;

    // dist(-1で初期化), cntは呼び出し元でN個分の配列を与えること。connect_vtxsは空のvectorでよい。
    void bfs_(ll sv, vll &dist, vll &connect_vtxs, vll &cnt, vll &root, ll search_depth = 1000000000)
    {
        if (dist[sv] != -1) return;
        dll q = dll();
        q.pb(sv);
        dist[sv] = 0;
        connect_vtxs.pb(sv);
        cnt[sv] = 1;
        if (search_depth == 0) return;
        while (len(q) > 0) {
            ll p = q[0];
            q.popleft();
            if (!EXIST(p, edges_)) continue;
            vector<pll> &evw = edges_[p];
            for (const auto& [ev, w] : evw) {
                bool isignore = false;
                rep(i, len(ignore_edges_[p])) {
                    const auto& [igev, igw] = ignore_edges_[p][i];
                    if (ev == igev && w == igw) {
                        isignore = true;
                    }
                }
                if (isignore) continue;

                if (dist[ev] != -1) {
                    if (dist[ev] == dist[p] + 1) {
                        cnt[ev] += cnt[p];
                        cnt[ev] %= ansmod_;
                    }
                    continue;
                }
                dist[ev] = dist[p] + 1;
                root[ev] = p;
                cnt[ev] = cnt[p];
                connect_vtxs.pb(ev);
                if (dist[ev] < search_depth)
                {
                    if (w == 0) q.pf(ev);
                    else q.pb(ev);
                }
            }
        }
    }

    // 木で無向辺のみ対応
    void dfs_(ll sv, ll pre = -1) {
        connect_vtxs_.pb(sv);
        root_[sv] = pre;
        traverse_preorder_path_.pb(sv);
        vector<pll> &evw = edges_[sv];
        ll child_cnt = 0;
        for (const auto& [ev, w] : evw) {
            if (ev == pre) continue;

            bool isignore = false; // 無効化されている辺は無視する。
            rep(i, len(ignore_edges_[sv])) {
                const auto& [igev, igw] = ignore_edges_[sv][i];
                if (ev == igev && w == igw) {
                    isignore = true;
                }
            }
            if (isignore) continue;

            dfs_(ev, sv);
            child_cnt++;
        }
        if (child_cnt == 0) { // 辺が1つのときで根でないとき
            traverse_reached_[sv] = true;
            traverse_inorder_path_.pb(sv);
        }
        if (pre != -1 && !traverse_reached_[pre]) {
            traverse_reached_[pre] = true;
            traverse_inorder_path_.pb(pre);
        }
        traverse_postorder_path_.pb(sv);
    }

public:
    vll path_; // dfsでたどった経路
    vll traverse_preorder_path_; // dfsでたどり着けるノード順 (行きがけ順)
    vll traverse_inorder_path_; // dfsでたどり着けるノード順 (通りがけ順)
    vll traverse_postorder_path_; // dfsでたどり着けるノード順 (帰りがけ順) (木DPで使えそう)
    vector<bool> traverse_reached_; // dfsでたどり着いたチェック
    vll dist_;
    vll connect_vtxs_;
    vll cnt_;
    vll root_;

    Graph(ll V, bool dir, ll ansmod = 1000000007) : V_(V), dir_(dir), ansmod_(ansmod), traverse_reached_(V_, false), dist_(V_, -1), cnt_(V_), root_(V_, -1){
        outdeg_ = vll(V);
        indeg_ = vll(V);
    }

    void append_edge(ll sv, ll ev, ll weight = 1)
    {
        vector<pll> &u = edges_[sv];
        pll v = make_pair(ev, weight);
        u.pb(v);
        outdeg_[sv]++;
        indeg_[ev]++;

        if (!dir_) {
            swap(sv, ev);
            outdeg_[sv]++;
            indeg_[ev]++;
            vector<pll> &ru = edges_[sv];
            pll rv = make_pair(ev, weight);
            ru.pb(rv);
        }
    }

    void ignore_edge(ll sv, ll ev, ll weight = 1) {
        vector<pll> &u = ignore_edges_[sv];
        pll v = make_pair(ev, weight);
        u.pb(v);
        if (!dir_) {
            swap(sv, ev);
            vector<pll> &ru = ignore_edges_[sv];
            pll rv = make_pair(ev, weight);
            ru.pb(rv);
        }
    }

    void ignore_edge_clear() {
        ignore_edges_.clear();
    }

    void bfs(ll sv, bool reset = true, ll search_depth = 1000000000) {
        if (reset) {
            rep(i, len(connect_vtxs_)) {
                dist_[connect_vtxs_[i]] = -1;
                cnt_[connect_vtxs_[i]] = 0;
                root_[connect_vtxs_[i]] = -1;
            }
            connect_vtxs_.clear();
        }
        bfs_(sv, dist_, connect_vtxs_, cnt_, root_, search_depth);
    }

    void dfs(ll sv, bool reset = false) {
        if (traverse_reached_[sv]) return; // すでに到達済みの点はdfsしない
        if (reset) {
            traverse_preorder_path_.clear();
            traverse_inorder_path_.clear();
            traverse_postorder_path_.clear();
            rep(i, len(connect_vtxs_)) {
                traverse_reached_[connect_vtxs_[i]] = false; // 「他の始点から到達してたときは無視したい」場合はこれをコメントアウト
                root_[connect_vtxs_[i]] = -1;
            }
            connect_vtxs_.clear();
        }
        dfs_(sv);
    }

    vll topo_sort()
    {
        heapqll q;
        vll to = vll(V_);
        vll topo_vertex_list;
        repdict(u, vtxs, edges_) {
            for (const auto& [ev, w] : vtxs) {
                ++to[ev];
            }
        }
        rep(i, V_) {
            if (to[i] != 0) continue;
            q.push(i);
        }
        while (len(q) != 0) {
            const ll v = q.top();
            q.pop();
            topo_vertex_list.pb(v);
            for (const auto [ev, w] : edges_[v]) {
                --to[ev];
                if (to[ev]) continue;
                q.push(ev);
            }
        }
        return topo_vertex_list;
    }

    ll longest_path() { // 有向グラフで非連結グラフの最大パスの長さを求める。
        dll q;
        vll dist(V_);
        rep (i, V_) {
            if (indeg_[i] == 0) q.pb(i);
        }
        while (len(q) != 0) {
            const ll u = q.front();
            q.pop_front();
            vector<pll> &v = edges_[u];
            rep (i, len(v)) {
                chmax(dist[v[i].first], dist[u] + 1);
                indeg_[v[i].first]--;
                if (indeg_[v[i].first] == 0) q.pb(v[i].first);
            }
        }

        return MAX(dist);
    }

    // 無向グラフのみ対応。
    // start->endのパスが無ければ空を返す
    vll get_path(ll start, ll end, ll vertexidx_offset = 0) {
        bfs(start);
        if (dist_[end] == -1) return vll{};
        ll pos = end;
        vll path = {end + vertexidx_offset};
        while(pos != start) {
            pos = root_[pos];
            path.pb(pos + vertexidx_offset);
        }
        REV(path);
        return path;
    }

    // 先にbfsを実行しておく。
    vll parts_tree_size() {
        vvll tmp;
        rep (i, V_) {
            tmp.pb(vll{dist_[i], i});
        }
        SORT(tmp);
        REV(tmp);

        vll ans(V_);
        rep (i, V_) {
            INI2(d, idx, tmp[i]);
            UNUSED(d);
            if (root_[idx] != -1) ans[root_[idx]] += ans[idx] + 1;
        }
        return ans;
    }
};

#include __FILE__
#endif