#include using namespace std; template using vp = vector>; template using pque = priority_queue; template using lpque = priority_queue,greater>; using ll = long long; using pint = pair; using pll = pair; using pil = pair; using pli = pair; using vint = vector; using vll = vector; using vpint = vector; using vpll = vector; using vpil = vector; using vpli = vector; using qint = queue; using pqint = pque; using qll = queue; using pqll = pque; constexpr double PI = 3.141592653589793; constexpr int INTINF = (1<<30)-1; constexpr ll LLINF = (1LL<<62)-1; constexpr int MPRIME = 1000000007; constexpr int MPRIME9 = 998244353; constexpr ll MMPRIME = (1LL<<61)-1; constexpr char newl = '\n'; #define len length() #define pushb push_back #define fi first #define se second #define all(name) name.begin(),name.end() #define rall(name) name.rbegin(),name.rend() #define gsort(vbeg,vend) sort(vbeg,vend,greater<>()) template struct matrix{ private: vector> m; public: matrix() : m(0, vector(0)) {} matrix(int h, int w) : m(h, vector(w)) {} matrix(int h, int w, const T &init) : m(h, vector(w, init)) {} void assign(int h, int w) { m = vector(h, vector(w)); } void assign(int h, int w, const T init) { m = vector(h, vector(w, init)); } void in() { for(int i=0; i>m[i][j]; } void out() { for(int i=0; i &operator[](int idx) { assert(0<=idx && idx inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template inline void init(T& v) { for(auto &a: v) cin>>a; } template inline void init(vector>& v) { for(auto &a: v) cin>>a.first>>a.second; } template inline void init(T& v, N n) { v.resize(n); for(auto &a: v) cin>>a; } template inline void init(vector>& v, N n) { v.resize(n); for(auto &a: v) cin>>a.first>>a.second; } template inline void out(T a) { cout< inline void out(T a, U... alist) { cout<(alist)...); } template void resiz(N n) { //empty } template void resiz(N n, T&& hd, U&&... tl) { hd.resize(n); resiz(n,forward(tl)...); } long long binpow(long long a, long long ex, long long p=MMPRIME) { long long res = 1; while(ex > 0) { if(ex & 1) (res*=a) %= p; ex>>=1; (a*=a) %= p; } return res; } string S; void input() { cin>>S; } void solve() { cout<<(S.length()+1)/2<