// made by https://github.com/094-gengar/add_lib_to_templ

#line 2 "cpplib/_other/bit.cpp"
#define LL long long

#define bitfor(bit, n) for (LL bit = 0; bit < (1 << n); bit++)
#define bitif(bit, a) if (bit & (1 << a))
LL bitsum(LL bit)
{
	LL r = 0;
	for(LL i = 1; i <= bit; i <<= 1)
		if(i & bit)
			r++;
	return r;
}

#line 2 "cpplib/_other/caesar.hpp"
#include <iostream>

struct caesar
{
	char c = 'a';
	int to_i() { return (caesar::c - 'a'); }
	int absolute(caesar& d) { return (d.c - caesar::c + 26) % 26; }
	friend std::istream& operator>>(std::istream& is, caesar& c) { is >> c.c; return is; }
	friend std::ostream& operator<<(std::ostream& os, caesar& c) { return os << c.c; }
};

struct Caesar
{
	char c = 'A';
	int to_i() { return (Caesar::c - 'A'); }
	int absolute(Caesar& d) { return (d.c - Caesar::c + 26) % 26; }
	friend std::istream& operator>>(std::istream& is, Caesar& c) { is >> c.c; return is; }
	friend std::ostream& operator<<(std::ostream& os, Caesar& c) { return os << c.c; }
};


#line 2 "cpplib/_other/template.hpp"
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <random>
//#define INCLUDE_BOOST
#ifdef INCLUDE_BOOST
#if __has_include(<boost/range/irange.hpp>)
#include <boost/range/irange.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/classification.hpp>
#endif

#endif
#pragma GCC target("avx512f")
#pragma GCC optimize("O3")
//#define int long long
#define LL long long
#define UL unsigned long long
#define itn int
#define INT(...)     \
	int __VA_ARGS__; \
	in(__VA_ARGS__)
#define LLL(...)    \
	LL __VA_ARGS__; \
	in(__VA_ARGS__)
#define I32(...)     \
	i32 __VA_ARGS__; \
	in(__VA_ARGS__)
#define I64(...)     \
	i64 __VA_ARGS__; \
	in(__VA_ARGS__)
#define U32(...)     \
	u32 __VA_ARGS__; \
	in(__VA_ARGS__)
#define U64(...)     \
	u64 __VA_ARGS__; \
	in(__VA_ARGS__)
#define STR(...)        \
	string __VA_ARGS__; \
	in(__VA_ARGS__)
#define CHR(...)      \
	char __VA_ARGS__; \
	in(__VA_ARGS__)
#define DBL(...)        \
	double __VA_ARGS__; \
	in(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define Sort(x) sort(all(x))
#define rSort(x)  \
	sort(all(x)); \
	reverse(all(x))
#define UNIQUE(v) v.erase(unique(all(v)), v.end())
#define uniq(v)   \
	sort(all(v)); \
	UNIQUE(v)
#define l_b(c, x) distance(c.begin(), lower_bound(all(c), (x)))
#define u_b(c, x) distance(c.begin(), upper_bound(all(c), (x)))
#define fi first
#define se second
#define mkpr make_pair
#define pb push_back
#define eb emplace_back
#define pass
#define aauto auto &&
#define cauto const auto &
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (usize i = (a), __B_SIZE__ = (b); i < __B_SIZE__; i++)
#define _per(i, n) peri(i, n, 0)
#define peri(i, a, b) for (int i = (a), __B_SIZE__ = (b); i >= __B_SIZE__; i--)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define per(...) _overload3(__VA_ARGS__, peri, _per, )(__VA_ARGS__)
#define bitshift(n) (1LL << (n))
#define myceil(a, b) ((a) + ((b)-1)) / (b)

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vLL = std::vector<LL>;
using vvLL = std::vector<vLL>;
using vb = std::vector<bool>;
using vvb = std::vector<vb>;
using vd = std::vector<double>;
using vvd = std::vector<vd>;
using vc = std::vector<char>;
using vvc = std::vector<vc>;
using vs = std::vector<std::string>;
using P = std::pair<int, int>;
using vp = std::vector<P>;
using pi32 = std::pair<i32, i32>;
using pLL = std::pair<LL, LL>;
using vpi32 = std::vector<pi32>;
using vpLL = std::vector<pLL>;

template <class T>
inline bool chmin(T& a, const T& b)
{
	if(b < a)
	{
		a = b;
		return true;
	}
	return false;
}
template <class T>
inline bool chmax(T& a, const T& b)
{
	if(a < b)
	{
		a = b;
		return true;
	}
	return false;
}
int Scan() { return getchar(); }
void Scan(signed& a) { scanf("%d", &a); }
void Scan(unsigned& a) { scanf("%u", &a); }
void Scan(long& a) { scanf("%ld", &a); }
void Scan(long long& a) { scanf("%lld", &a); }
void Scan(unsigned long long& a) { scanf("%llu", &a); }
void Scan(char& a)
{
	do
	{
		a = getchar();
	} while(a == ' ' || a == '\n');
}
void Scan(float& a) { scanf("%f", &a); }
void Scan(double& a) { scanf("%lf", &a); }
void Scan(long double& a) { scanf("%Lf", &a); }
void Scan(std::string& a) { std::cin >> a; }
template <class T>
void Scan(std::vector<T>&);
template <class T, class U>
void Scan(std::pair<T, U>&);
template <class T>
void Scan(std::vector<T>& a)
{
	for(auto&& i : a)
		Scan(i);
}
template <class T, class U>
void Scan(std::pair<T, U>& a)
{
	Scan(a.first);
	Scan(a.second);
}
template <class T>
void Scan(T& a) { std::cin >> a; }
void in() {}
template <class Car, class... Cdr>
void in(Car&& car, Cdr &&...cdr)
{
	Scan(car);
	in(std::forward<Cdr>(cdr)...);
}

void Print() { putchar(' '); }
void Print(signed a) { printf("%d", a); }
void Print(bool a) { printf("%d", a); }
void Print(unsigned a) { printf("%u", a); }
void Print(long a) { printf("%ld", a); }
void Print(long long a) { printf("%lld", a); }
void Print(unsigned long long a) { printf("%llu", a); }
void Print(char a) { printf("%c", a); }
void Print(float a) { printf("%f", a); }
void Print(double a) { printf("%lf", a); }
void Print(long double a) { printf("%Lf", a); }
void Print(const std::string& a)
{
	for(auto&& i : a)
		Print(i);
}
template <class T>
void Print(const std::vector<T>&);
template <class T, class U>
void Print(const std::pair<T, U>&);
template <class T>
void Print(const std::vector<T>& a)
{
	if(a.empty())
		return;
	Print(a[0]);
	for(auto i = a.begin(); ++i != a.end();)
	{
		putchar(' ');
		Print(*i);
	}
}
template <class T, class U>
void Print(const std::pair<T, U>& a)
{
	Print(a.first);
	putchar(' ');
	Print(a.second);
}
template <class T>
void Print(const T& a) { std::cout << a; }
void out() { putchar('\n'); }
template <class T>
void out(const T& t)
{
	Print(t);
	putchar('\n');
}
template <class Car, class... Cdr>
void out(Car& car, Cdr &...cdr)
{
	Print(car);
	putchar(' ');
	out(std::forward<Cdr>(cdr)...);
}

void println() { printf("\n"); }
void println(signed x) { printf("%d\n", x); }
void println(bool x) { printf("%d\n", x); }
void println(unsigned x) { printf("%u\n", x); }
void println(long x) { printf("%ld\n", x); }
void println(long long x) { printf("%lld\n", x); }
void println(unsigned long long x) { printf("%llu\n", x); }
void println(char x) { printf("%c\n", x); }
void println(float x) { printf("%.15f\n", x); }
void println(double x) { printf("%.15lf\n", x); }
template <class T>
void println(T x) { std::cout << x << '\n'; }

#define writeln(x) println(x)

void yn(bool fl = true)
{
	out(fl ? "Yes" : "No");
}
template <class T>
void drop(T x)
{
	std::cout << (x) << std::endl;
	exit(0);
}
void dYes()
{
	std::flush(std::cout);
	puts("Yes");
	fflush(stdout);
	exit(0);
}
void dNo()
{
	std::flush(std::cout);
	puts("No");
	fflush(stdout);
	exit(0);
}
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
LL fact(LL n, LL m)
{
	LL f = n;
	for(LL i = n - 1; i >= 1; i--)
	{
		f *= i;
		f %= m;
	}
	return f;
}
constexpr LL inf = 0x1fffffffffffffff;
constexpr LL mod = 1000000007LL;
constexpr LL mod2 = 998244353LL;
constexpr double eps = 1e-8;
constexpr double pi = 3.141592653589793238462643383279;


#line 2 "cpplib/Graph/LCA.cpp"
#include <vector>
struct LCA
{
	std::vector<std::vector<int>> par;
	std::vector<int> dis;
	LCA(const std::vector<std::vector<int>>& g, int root = 0) { init(g, root); }
	void init(const std::vector<std::vector<int>>& g, int root = 0)
	{
		int v = g.size(), k = 1;
		for(; 1 << k < v; k++)
			;
		par.assign(k, std::vector<int>(v, -1));
		dis.assign(v, -1);
		dfs(g, root, -1, 0);
		for(int i = 0; i < k - 1; i++)
			for(int j = 0; j < v; j++)
			{
				if(par[i][j] < 0)
					par[i + 1][j] = -1;
				else
					par[i + 1][j] = par[i][par[i][j]];
			}
	}
	void dfs(const std::vector<std::vector<int>>& g, int v, int p, int d)
	{
		par[0][v] = p;
		dis[v] = d;
		for(int e : g[v])
			if(e != p)
				dfs(g, e, v, d + 1);
	}
	int run(int u, int v)
	{
		if(dis[u] < dis[v])
			std::swap(u, v);
		int k = par.size();
		for(int i = 0; i < k; i++)
			if(dis[u] - dis[v] >> i & 1)
				u = par[i][u];
		if(u == v)
			return u;
		for(int i = k - 1; i >= 0; i--)
			if(par[i][u] != par[i][v])
			{
				u = par[i][u];
				v = par[i][v];
			}
		return par[0][u];
	}
	int getdis(int u, int v) { return dis[u] + dis[v] - dis[run(u, v)] * 2; }
	bool isonpath(int u, int v, int a) { return getdis(u, a) + getdis(a, v) == getdis(u, v); }
};


#line 2 "cpplib/Graph/oreore_graph.hpp"
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
/*
template <class T>
inline bool chmin(T& a, const T& b)
{
	if(b < a)
	{
		a = b;
		return true;
	}
	return false;
}
*/
template <class T>
struct oreore_graph
{
	int _n;
	bool _idx;
	bool _drc;
	std::vector<std::vector<T>> _g;
	oreore_graph(int n, bool drc = false, bool idx = 1)
		: _n(n), _drc(drc), _idx(idx), _g(n)
	{
	}
	void init(int m)
	{
		T a, b;
		for(int i = 0; i < m; i++)
		{
			scanf("%d %d", &a, &b);
			a -= _idx;
			b -= _idx;
			_g[a].emplace_back(b);
			if(!_drc)
				_g[b].emplace_back(a);
		}
	}
	std::vector<T> bfs(T s, T t = -1)
	{
		std::vector<T> dis(_n, 1ll << 29);
		std::vector<bool> vis(_n, false);
		dis[s] = 0;
		std::queue<T> q;
		q.emplace(s);
		while(q.size())
		{
			T cur = q.front();
			q.pop();
			for(auto e : _g[cur])
				if(chmin(dis[e], dis[cur] + 1))
					q.emplace(e);
		}
		if(t == -1)
			return dis;
		else
			return std::vector<T>{dis[t]};
	}
};

template <class T>
struct oreore_weighted_graph
{
	using ptt = std::pair<T, T>;
	int _n;
	bool _idx;
	bool _drc;
	std::vector<std::vector<ptt>> _g;
	oreore_weighted_graph(int n, bool drc = false, bool idx = 1)
		: _n(n), _drc(drc), _idx(idx), _g(n)
	{
	}
	void init(int m, bool cst = true)
	{
		T a, b, c = 1;
		for(int i = 0; i < m; i++)
		{
			if(cst)
				scanf("%d %d %d", &a, &b, &c);
			else
				scanf("%d %d", &a, &b);
			a -= _idx;
			b -= _idx;
			_g[a].emplace_back(c, b);
			if(!_drc)
				_g[b].emplace_back(c, a);
		}
	}
	std::vector<T> bfs(T s, T t = -1)
	{
		std::vector<T> dis(_n, 1ll << 29);
		std::vector<bool> vis(_n, false);
		dis[s] = 0;
		std::queue<ptt> q;
		q.emplace(0, s);
		while(q.size())
		{
			ptt cur = q.front();
			q.pop();
			if(cur.first > dis[cur.second])
				continue;

			for(auto e : _g[cur.second])
				if(chmin(dis[e.second], dis[cur.second] + e.first))
					q.emplace(dis[e.second], e.second);
		}
		if(t == -1)
			return dis;
		else
			return std::vector<T>{dis[t]};
	}

	std::vector<T> dijkstra(T s, T t = -1)
	{
		std::vector<T> dis(_n, 1ll << 29);
		std::vector<bool> vis(_n, false);
		dis[s] = 0;
		std::priority_queue<ptt, std::vector<ptt>, std::greater<>> pq;
		pq.emplace(0, s);
		while(pq.size())
		{
			ptt cur = pq.top();
			pq.pop();
			if(cur.first > dis[cur.second])
				continue;
			for(auto e : _g[cur.second])
				if(chmin(dis[e.second], dis[cur.second] + e.first))
					pq.emplace(dis[e.second], e.second);
		}
		if(t == -1)
			return dis;
		else
			return std::vector<T>{dis[t]};
	}
};


#line 2 "cpplib/math/argsort.hpp"
#include <vector>
#include <algorithm>

struct Ray
{
	long long x, y;
	bool operator<(const Ray& r) const { return x * r.y > y * r.x; }
	bool operator<=(const Ray& r) const { return x * r.y >= y * r.x; }
};

std::vector<std::pair<Ray, Ray>> argSort(std::vector<std::pair<long long, long long>> xy)
{
	std::vector<std::pair<Ray, Ray>> p;
	for(auto [x, y] : xy)
		p.push_back(std::make_pair(Ray{x - 1, y}, Ray{x, y - 1}));
	std::sort(p.begin(), p.end());
	return p;
}


#line 2 "cpplib/math/comb.hpp"
#include <vector>

template <class T>
struct COMB
{
	long long n;
	std::vector<T> fa, ifa;
	COMB(long long n_) : n(n_)
	{
		fa.resize(n + 1);
		ifa.resize(n + 1);
		fa[0] = 1;
		for(long long i = 1; i <= n; i++)
			fa[i] = fa[i - 1] * i;
		ifa[n] = (T)(1) / fa[n];
		for(long long i = n - 1; i >= 0; i--)
			ifa[i] = ifa[i + 1] * (i + 1);
	}
	T comb(long long n, long long r)
	{
		return n < 0 || r < 0 || n < r ? (T)(0) : fa[n] * ifa[r] * ifa[n - r];
	}
};

#line 2 "cpplib/math/ksb.hpp"
#include <vector>
#include <map>

std::map<long long, long long> ksb(std::vector<long long> ns)
{
	std::map<long long, long long> m;
	for(auto n : ns)
	{
		for(long long i = 2; i * i <= n; i++)
		{
			long long tmp = 0;
			while(n % i == 0)
			{
				tmp++;
				n /= i;
			}
			if(0 != tmp)
				m[i]++;
			if(n == 1)
				break;
		}
		if(1 != n)
			m[n]++;
	}
	return m;
}

#line 2 "cpplib/math/modint.hpp"
template <long long Mod>
struct modInt
{
	long long x;
	constexpr modInt() noexcept : x() {}
	template <class T>
	constexpr modInt(T v = 0) noexcept : x(v% Mod)
	{
		if(x < 0)
			x += Mod;
	}
	constexpr long long getval() const noexcept { return x; }
	constexpr modInt operator-() const noexcept { return x ? Mod - x : 0; }
	constexpr modInt operator+(const modInt& r) const noexcept { return modInt(*this) += r; }
	constexpr modInt operator-(const modInt& r) const noexcept { return modInt(*this) -= r; }
	constexpr modInt operator*(const modInt& r) const noexcept { return modInt(*this) *= r; }
	constexpr modInt operator/(const modInt& r) const noexcept { return modInt(*this) /= r; }
	constexpr modInt& operator+=(const modInt& r) noexcept
	{
		x += r.x;
		if(x >= Mod)
			x -= Mod;
		return *this;
	}
	constexpr modInt& operator-=(const modInt& r) noexcept
	{
		x -= r.x;
		if(x < 0)
			x += Mod;
		return *this;
	}
	constexpr modInt& operator*=(const modInt& r) noexcept
	{
		x = x * r.x % Mod;
		return *this;
	}
	constexpr modInt& operator/=(const modInt& r) noexcept
	{
		x = x * r.inv().getval() % Mod;
		return *this;
	}
	constexpr modInt powm(long long n) noexcept
	{
		if(n < 0)
			return powm(-n).inv();
		modInt x = *this, r = 1;
		for(; n; x *= x, n >>= 1)
			if(n & 1)
				r *= x;
		return r;
	}
	constexpr modInt inv() const noexcept
	{
		long long a = x, b = Mod, u = 1, v = 0;
		while(b)
		{
			long long t = a / b;
			a -= t * b;
			std::swap(a, b);
			u -= t * v;
			std::swap(u, v);
		}
		return modInt(u);
	}
	constexpr modInt comb(long long a) noexcept
	{
		modInt n = *this, s = 1;
		for(int i = 0; i < a; i++)
			s *= (n - modInt(i));
		modInt m = 1;
		for(int i = 1; i <= a; i++)
			m *= modInt(i);
		return s * m.powm(Mod - 2); //Fermat's little thm
	}
	constexpr bool operator==(const modInt& r) { return this->x == r.x; }
	constexpr bool operator!=(const modInt& r) { return this->x != r.x; }
	friend std::ostream& operator<<(std::ostream& os, const modInt<Mod>& a) { return os << a.x; }
	friend std::istream& operator>>(std::istream& is, modInt<Mod>& a)
	{
		long long v;
		is >> v;
		a = modInt<Mod>(v);
		return is;
	}
};

//const long long mod=1000000007;
//using mint=modInt<mod>;
using mint = modInt<1000000007>;
using mint2 = modInt<998244353>;

#line 2 "cpplib/math/modinv.hpp"
long long modpow(long long a, long long b, long long mod)
{
	a %= mod;
	long long r = 1;
	while(b)
	{
		r = r * ((b % 2) ? a : 1) % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return r;
}

long long modinv(long long a, long long mod)
{
	return modpow(a, mod - 2, mod);
}


#line 2 "cpplib/math/primefact.hpp"
#include <vector>

template <class T>
std::vector<std::pair<T, T>> prime_factor(T n)
{
	std::vector<std::pair<T, T>> ret;
	for(T i = 2; i * i <= n; i++)
	{
		if(n % i != 0)
			continue;
		T tmp = 0;
		while(n % i == 0)
		{
			tmp++;
			n /= i;
		}
		ret.push_back(make_pair(i, tmp));
	}
	if(n != 1)
		ret.push_back(make_pair(n, 1));
	return ret;
}


#line 2 "cpplib/Structure/binaryheap.hpp"

#include <vector>
//bheap
struct bheap
{
	std::vector<long> _a;
	bheap() { _a.push_back(0L); }
	void push(long _x)
	{
		_a.push_back(_x);
		long pos = _a.size() - 1;
		for(; pos > 1 && _a[pos] < _a[pos / 2]; std::swap(_a[pos], _a[pos / 2]), pos /= 2)
			;
	}
	void pop()
	{
		_a[1] = _a[_a.size() - 1];
		_a.pop_back();
		if(_a.size() == 1)
			return;
		long pos = 1, lc, rc;
		for(; (lc = pos * 2) < _a.size();)
		{
			rc = lc + 1;
			if(lc == _a.size() - 1)
			{
				if(_a[pos] > _a[lc])
				{
					std::swap(_a[pos], _a[lc]);
					pos = lc;
				}
				else
				{
					break;
				}
			}
			else
			{
				if(_a[lc] < _a[rc])
				{
					if(_a[lc] < _a[pos])
					{
						std::swap(_a[pos], _a[lc]);
						pos = lc;
					}
					else
					{
						break;
					}
				}
				else
				{
					if(_a[rc] < _a[pos])
					{
						std::swap(_a[pos], _a[rc]);
						pos = rc;
					}
					else
					{
						break;
					}
				}
			}
		}
	}
	long getmin() { return _a[1]; }
	long siz() { return _a.size() - 1; }
	void cl()
	{
		_a.clear();
		_a.push_back(0L);
	}
};


#line 2 "cpplib/Structure/BinaryIndexedTree.hpp"
#include <vector>
//BinaryIndexedTree(1-indexed)
template <class T>
struct BIT
{
	int n;
	std::vector<T> B_I_T;
	BIT(int n_ = 0, T init = 0) : n(n_), B_I_T(n_ + 1, init) {}
	T sum(int i)
	{
		T ans = 0;
		for(; i > 0; i -= i & -i)
			ans += B_I_T[i];
		return ans;
	}
	void add(int i, T a)
	{
		if(!i)
			return;
		for(; i <= n; i += i & -i)
			B_I_T[i] += a;
	}
	int l_b_B_I_T(T k)
	{
		if(k <= 0)
			return 0;
		int ret = 0, i = 1;
		for(; (i << 1) <= n; i <<= 1)
			;
		for(; i; i >>= 1)
			if(ret + i <= n && B_I_T[ret + i] < k)
				k -= B_I_T[ret += i];
		return (ret + 1);
	}
};

#line 2 "cpplib/Structure/compress_vector.hpp"
template <class T>
struct compress_vector
{
	int n;
	std::vector<T> a;
	compress_vector(int n_) : n(n_), a(n_) {};
	void compress()
	{
		std::map<T, T> mp;
		for(int i = 0; i < n; i++)
			mp[a[i]] = -1;
		int c = 0;
		for(auto& p : mp)
			p.second = c++;
		for(int i = 0; i < n; i++)
			a[i] = mp[a[i]];
	}
};

#line 2 "cpplib/Structure/dynamic_connectivity.hpp"
#include <iostream>
#include <vector>
#include <functional>
#include <unordered_set>
#include <unordered_map>

#define LL long long

template<class T>
class dynamic_connectivity
{
	class euler_tour_tree
	{
	public:
		struct node;
		using nodeP = node*;

		struct node
		{
			nodeP ch[2] = {nullptr, nullptr};
			nodeP p = nullptr;
			int l, r, sz;
			T val = et, sum = et;
			bool exact;
			bool child_exact;
			bool edge_connected = false;
			bool child_edge_connected = false;
			node() {}
			node(int l, int r) : l(l), r(r), sz(l == r), exact(l < r), child_exact(l < r) {}
			bool is_root() { return !p; }
		};

		std::vector<std::unordered_map<int, nodeP>> ptr;

		nodeP get_node(int l, int r)
		{
			if(ptr[l].find(r) == ptr[l].end()) ptr[l][r] = new node(l, r);
			return ptr[l][r];
		}

		nodeP root(nodeP t)
		{
			if(!t) return t;
			while(t->p) t = t->p;
			return t;
		}

		bool same(nodeP s, nodeP t)
		{
			if(s) splay(s);
			if(t) splay(t);
			return root(s) == root(t);
		}

		nodeP reroot(nodeP t)
		{
			auto s = split(t);
			return merge(s.second, s.first);
		}

		std::pair<nodeP, nodeP> split(nodeP s)
		{
			splay(s);
			nodeP t = s->ch[0];
			if(t) t->p = nullptr;
			s->ch[0] = nullptr;
			return std::make_pair(t, update(s));
		}

		std::pair<nodeP, nodeP> split2(nodeP s)
		{
			splay(s);
			nodeP t = s->ch[0];
			nodeP u = s->ch[1];
			if(t) t->p = nullptr;
			s->ch[0] = nullptr;
			if(u) u->p = nullptr;
			s->ch[1] = nullptr;
			return std::make_pair(t, u);
		}

		std::tuple<nodeP, nodeP, nodeP> split(nodeP s, nodeP t)
		{
			auto u = split2(s);
			if(same(u.first, t))
			{
				auto r = split2(t);
				return std::make_tuple(r.first, r.second, u.second);
			}
			else
			{
				auto r = split2(t);
				return std::make_tuple(u.first, r.first, r.second);
			}
		}

		template<class Car, class... Cdr>
		nodeP merge(Car car, Cdr... cdr)
		{
			return merge(car, merge(cdr...));
		}

		nodeP merge(nodeP s, nodeP t)
		{
			if(!s) return t;
			if(!t) return s;
			while(s->ch[1]) s = s->ch[1];
			splay(s);
			s->ch[1] = t;
			if(t) t->p = s;
			return update(s);
		}

		int size(nodeP t) { return t ? t->sz : 0; }

		nodeP update(nodeP t)
		{
			t->sum = et;
			if(t->ch[0]) t->sum = fn(t->sum, t->ch[0]->sum);
			if(t->l == t->r) t->sum = fn(t->sum, t->val);
			if(t->ch[1]) t->sum = fn(t->sum, t->ch[1]->sum);

			t->sz = size(t->ch[0]) + (int)(t->l == t->r) + size(t->ch[1]);
			t->child_edge_connected = (
				t->ch[0] ? t->ch[0]->child_edge_connected : 0
				) | (t->edge_connected) | (
					t->ch[1] ? t->ch[1]->child_edge_connected : 0
					);
			t->child_exact = (
				t->ch[0] ? t->ch[0]->child_exact : 0
				) | (t->exact) | (
					t->ch[1] ? t->ch[1]->child_exact : 0
					);

			return t;
		}

		void push(nodeP t) {}

		void rot(nodeP t, bool b)
		{
			nodeP x = t->p, y = x->p;
			if(x->ch[1 - b] = t->ch[b]) t->ch[b]->p = x;
			t->ch[b] = x, x->p = t;
			update(x);
			update(t);
			if(t->p = y)
			{
				if(y->ch[0] == x) y->ch[0] = t;
				if(y->ch[1] == x) y->ch[1] = t;
				update(y);
			}
		}

		void splay(nodeP t)
		{
			push(t);
			while(!t->is_root())
			{
				nodeP q = t->p;

				if(q->is_root())
				{
					push(q);
					push(t);
					rot(t, (q->ch[0] == t));
				}
				else
				{
					nodeP r = q->p;
					push(r);
					push(q);
					push(t);
					bool b = (r->ch[0] == q);
					if(q->ch[1 - b] == t)
					{
						rot(q, b);
						rot(t, b);
					}
					else
					{
						rot(t, 1 - b);
						rot(t, b);
					}
				}
			}
		}

		void debug(nodeP t)
		{
			if(!t) return;
			debug(t->ch[0]);
			std::cerr << t->l << '-' << t->r << ' ';
			debug(t->ch[1]);
		}

	public:
		euler_tour_tree() {}
		euler_tour_tree(int sz)
		{
			ptr.resize(sz);
			for(int i = 0; i < sz; i++) ptr[i][i] = new node(i, i);
		}

		int size(int s)
		{
			nodeP t = get_node(s, s);
			splay(t);
			return t->sz;
		}

		bool same(int s, int t) { return same(get_node(s, s), get_node(t, t)); }

		void set_size(int sz)
		{
			ptr.resize(sz);
			for(int i = 0; i < sz; i++) ptr[i][i] = new node(i, i);
		}

		void update(int s, T x)
		{
			nodeP t = get_node(s, s);
			splay(t);
			t->val = fn(t->val, x);
			update(t);
		}

		void edge_update(int s, auto g)
		{
			nodeP t = get_node(s, s);
			splay(t);

			std::function<void(nodeP)> dfs = [&](nodeP t)
			{
				assert(t);
				if(t->l < t->r && t->exact)
				{
					splay(t);
					t->exact = 0;
					update(t);
					g(t->l, t->r);
					return;
				}

				if(t->ch[0] && t->ch[0]->child_exact) dfs(t->ch[0]);
				else dfs(t->ch[1]);
			};

			while(t && t->child_exact)
			{
				dfs(t);
				splay(t);
			}
		}

		bool try_reconnect(int s, auto f)
		{
			nodeP t = get_node(s, s);
			splay(t);
			std::function<bool(nodeP)> dfs = [&](nodeP t) -> bool
			{
				assert(t);
				if(t->edge_connected)
				{
					splay(t);
					return f(t->l);
				}

				if(t->ch[0] && t->ch[0]->child_edge_connected) return dfs(t->ch[0]);
				else return dfs(t->ch[1]);
			};

			while(t->child_edge_connected)
			{
				if(dfs(t)) return true;
				splay(t);
			}

			return false;
		}

		void edge_connected_update(int s, bool b)
		{
			nodeP t = get_node(s, s);
			splay(t);
			t->edge_connected = b;
			update(t);
		}

		bool link(int l, int r)
		{
			if(same(l, r)) return false;
			merge(reroot(get_node(l, l)), get_node(l, r), reroot(get_node(r, r)), get_node(r, l));
			return true;
		}

		bool cut(int l, int r)
		{
			if(ptr[l].find(r) == ptr[l].end()) return false;
			nodeP s, t, u;
			std::tie(s, t, u) = split(get_node(l, r), get_node(r, l));
			merge(s, u);
			nodeP p = ptr[l][r];
			nodeP q = ptr[r][l];
			ptr[l].erase(r);
			ptr[r].erase(l);

			delete p;
			delete q;

			return true;
		}

		T get_sum(int p, int v)
		{
			cut(p, v);
			nodeP t = get_node(v, v);
			splay(t);
			T res = t->sum;
			link(p, v);
			return res;
		}

		T get_sum(int s)
		{
			nodeP t = get_node(s, s);
			splay(t);
			return t->sum;
		}
	};
	int dep = 1;
	std::vector<euler_tour_tree> ett;
	std::vector<std::vector<std::unordered_set<int>>> edges;
	int sz;

public:
	dynamic_connectivity(int sz) : sz(sz)
	{
		ett.emplace_back(sz);
		edges.emplace_back(sz);
	}

	bool link(int s, int t)
	{
		if(s == t) return false;
		if(ett[0].link(s, t)) return true;
		edges[0][s].insert(t);
		edges[0][t].insert(s);
		if(edges[0][s].size() == 1) ett[0].edge_connected_update(s, 1);
		if(edges[0][t].size() == 1) ett[0].edge_connected_update(t, 1);

		return false;
	}

	bool same(int s, int t) { return ett[0].same(s, t); }

	int size(int s) { return ett[0].size(s); }

	std::vector<int> get_vertex(int s) { return ett[0].vertex_list(s); }

	void update(int s, T x) { ett[0].update(s, x); }

	T get_sum(int s) { return ett[0].get_sum(s); }

	bool cut(int s, int t)
	{
		if(s == t) return false;
		for(int i = 0; i < dep; i++)
		{
			edges[i][s].erase(t);
			edges[i][t].erase(s);
			if(edges[i][s].size() == 0) ett[i].edge_connected_update(s, 0);
			if(edges[i][t].size() == 0) ett[i].edge_connected_update(t, 0);
		}

		for(int i = dep - 1; i >= 0; i--)
		{
			if(ett[i].cut(s, t))
			{
				if(i == dep - 1)
				{
					dep++;
					ett.emplace_back(sz);
					edges.emplace_back(sz);
				}

				return !try_reconnect(s, t, i);
			}
		}

		return false;
	}

	bool try_reconnect(int s, int t, int k)
	{
		for(int i = 0; i < k; i++) ett[i].cut(s, t);

		for(int i = k; i >= 0; i--)
		{
			if(ett[i].size(s) > ett[i].size(t)) std::swap(s, t);
			auto g = [&](int s, int t) { ett[i + 1].link(s, t); };
			ett[i].edge_update(s, g);
			auto f = [&](int x) -> bool
			{
				for(auto itr = edges[i][x].begin(); itr != edges[i][x].end();)
				{
					auto y = *itr;
					itr = edges[i][x].erase(itr);
					edges[i][y].erase(x);

					if(edges[i][x].size() == 0) ett[i].edge_connected_update(x, 0);
					if(edges[i][y].size() == 0) ett[i].edge_connected_update(y, 0);

					if(ett[i].same(x, y))
					{
						edges[i + 1][x].insert(y);
						edges[i + 1][y].insert(x);
						if(edges[i + 1][x].size() == 1) ett[i + 1].edge_connected_update(x, 1);
						if(edges[i + 1][y].size() == 1) ett[i + 1].edge_connected_update(y, 1);
					}
					else
					{
						for(int j = 0; j <= i; j++) ett[j].link(x, y);
						return true;
					}
				}

				return false;
			};

			if(ett[i].try_reconnect(s, f)) return true;
		}
		return false;
	}

	constexpr static T et = T();
	constexpr static T fn(T s, T t) { return s + t; }
};


#line 2 "cpplib/Structure/HashMap.hpp"
#include <vector>
#include <string>
//hmap
struct hmap
{
	std::vector<std::vector<std::pair<std::string, int>>> l_;
	hmap() { l_.resize(10000, std::vector<std::pair<std::string, int>>(0)); }
	int gethash(std::string key)
	{
		int r = 0;
		for(int i = 0; i < key.length(); i++)
			r += key[i];
		return r % 10000 * 17 % 10000;
	}
	void put(std::string key, int val)
	{
		int id = gethash(key);
		if(l_[id].empty())
			l_[id].push_back(make_pair(key, val));
		else
		{
			auto& ar = l_[id];
			for(int i = 0; i < ar.size(); i++)
			{
				auto pr = ar[i];
				if(pr.first == key)
				{
					ar.erase(ar.begin() + i);
					break;
				}
			}
			ar.push_back(make_pair(key, val));
		}
	}
	int get(std::string key)
	{
		int id = gethash(key);
		if(l_[id].empty())
			return -1;
		else
		{
			auto& ar = l_[id];
			for(int i = 0; i < ar.size(); i++)
			{
				auto pr = ar[i];
				if(pr.first == key)
					return pr.second;
			}
			return -1;
		}
	}
	void rm(std::string key)
	{
		int id = gethash(key);
		if(l_[id].empty())
			return;
		auto& ar = l_[id];
		for(int i = 0; i < ar.size(); i++)
		{
			auto pr = ar[i];
			if(pr.first == key)
			{
				ar.erase(ar.begin() + i);
				break;
			}
		}
	}
};

#line 2 "cpplib/Structure/lazysegtree.hpp"
/*
TODO: 完成させる

//lazysegtree
template<typename X,typename M>struct lazyseg
{
	int n;
	std::function<X(X,X)>fx;
	std::function<X(X,M)>fa;
	std::function<X(M,M)>fm;
	const X ex;
	const M em;
	std::vector<X>d;
	std::vector<M>lazy;
	lazyseg
	(
		int n_,
		std::function<X(X,X)>fx_,
		std::function<X(X,M)>fa_,
		std::function<X(M,M)>fm_,
		X ex_,
		M em_
	):n(),fx(fx_),fa(fa_),fm(fm_),ex(ex_),em(em_),d(n_*4,ex),lazy(n_*4,em)
	{
		int x=1;
		while(n_>x)x*=2;
		n=x;
	}

	void set(int i,X x){d[i+n-1]=x;}
	void build(){for(int k=n-2;k>=0;k--)d[k]=fx(d[2*k+1],d[2*k+2]);}
	void eval(int k)
	{
		if(lazy[k]==em)return;
		if(k<n-1)
		{
			lazy[k*2+1]=fm(lazy[k*2+1],lazy[k]);
			lazy[k*2+2]=fm(lazy[k*2+2],lazy[k]);
		}
		d[k]=fa(d[k],lazy[k]);
		lazy[k]=em;
	}
	void update(int a,int b,M x,int k,int l,int r)
	{
		eval(k);
		if(a<=l&&r<=b)lazy[k]=fm(lazy[k],x),eval(k);
		else if(a<r&&l<b)
		{
			update(a,b,x,k*2+1,l,(l+r)/2);
			update(a,b,x,k*2+2,(l+r)/2,r);
			d[k]=fx(d[k*2+1],d[k*2+2]);
		}
	}
	void update(int a,int b,M x){update(a,b,x,0,0,n);}
	X qsub(int a,int b,int k,int l,int r)
	{
		eval(k);
		if(r<=a||b<=l)return ex;
		else if(a<=l&&r<=b)return d[k];
		else
		{
			X vl=qsub(a,b,k*2+1,l,(l+r)/2);
			X vr=qsub(a,b,k*2+2,(l+r)/2,r);
			return fx(vl,vr);
		}
	}
	X query(int a,int b){return qsub(a,b,0,0,n);}
};

//RMQ :
//int n=**size**
//auto fx=[](int a,int b)->int{return min(a,b);};
//auto fa=[](int x,int m)->int{return m;};
//auto fm=[](int m1,int m2)->int{return m2;};
//int ex=inf;
//int em=inf;
//lazyseg<int,int>rmq(n,fx,fa,fm,ex,em);
*/

#line 2 "cpplib/Structure/segtree.hpp"
// Segtree
template <class T>
struct segtree
{
	using F = std::function<T(T, T)>;
	int sz;
	std::vector<T> seg;
	const F f;
	const T m1;
	segtree(int n, const F f, const T& m1) : f(f), m1(m1)
	{
		for(sz = 1; sz < n; sz <<= 1)
			;
		seg.assign(2 * sz, m1);
	}
	void update(int k, const T& x)
	{
		k += sz;
		seg[k] = x;
		for(; k >>= 1;)
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
	}
	void set(int k, const T& x) { seg[k + sz] = x; }
	void build()
	{
		for(int k = sz - 1; k > 0; k--)
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
	}
	T query(int a, int b)
	{
		T L = m1, R = m1;
		for(a += sz, b += sz; a < b; a >>= 1, b >>= 1)
		{
			if(a & 1)
				L = f(L, seg[a++]);
			if(b & 1)
				R = f(seg[--b], R);
		}
		return f(L, R);
	}
	T operator[](const int& k) const { return seg[k + sz]; }
	template <class C>
	int find_subtree(int a, const C& check, T& M, bool type)
	{
		for(; a < sz;)
		{
			T nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
			if(check(nxt))
				a = 2 * a + type;
			else
				M = nxt, a = 2 * a + 1 - type;
		}
		return a - sz;
	}
	template <class C>
	int find_first(int a, const C& check)
	{
		T L = m1;
		if(a <= 0)
			return check(f(L, seg[1])) ? find_subtree(1, check, L, false) : -1;
		int b = sz;
		for(a += sz, b += sz; a < b; a >>= 1, b >>= 1)
		{
			if(a & 1)
			{
				T nxt = f(L, seg[a]);
				if(check(nxt))
					return find_subtree(a, check, L, false);
				L = nxt;
				a++;
			}
		}
		return -1;
	}
	template <class C>
	int find_last(int b, const C& check)
	{
		T R = m1;
		if(b >= sz)
			return check(f(seg[1], R)) ? find_subtree(1, check, R, true) : -1;
		int a = sz;
		for(b += sz; a < b; a >>= 1, b >>= 1)
		{
			if(b & 1)
			{
				T nxt = f(seg[--b], R);
				if(check(nxt))
					return find_subtree(b, check, R, true);
				R = nxt;
			}
		}
		return -1;
	}
};

// SegmentTree(n, f, M1):= サイズ n の初期化。
// f : 2つの区間の要素をマージする二項演算,
// M1 はモノイドの単位元である。
// set(k, x):= k 番目の要素に x を代入する。
// build():= セグメント木を構築する。
// query(a, b):= 区間 [a, b) に対して二項演算した結果を返す。
// update(k, x):= k 番目の要素を x に変更する。
// operator[k] := k 番目の要素を返す。
// find_first(a, check) := [a,x) が check を満たす最初の要素位置 x を返す。
// find_last(b, check) := [x,b) が check を満たす最後の要素位置 x を返す。
// for example : segtree<int>seg(n,[](int a,int b){return min(a,b);},INT32_MAX);


#line 2 "cpplib/Structure/union-find.hpp"
#include <vector>
#include <algorithm>
//union-find
struct uni
{
	int n_;
	std::vector<int> par, siz;
	uni(int n) : n_(n), par(n), siz(n, 1LL)
	{
		for(int i = 0; i < n; i++)
			par[i] = i;
	}
	void init(int n)
	{
		par.resize(n);
		siz.assign(n, 1LL);
		for(int i = 0; i < n; i++)
			par[i] = i;
	}
	void merge(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if(rx == ry)
			return;
		if(siz[rx] < siz[ry])
			std::swap(rx, ry);
		siz[rx] += siz[ry];
		par[ry] = rx;
		return;
	}
	int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }
	bool same(int x, int y) { return root(x) == root(y); }
	int size(int x) { return siz[root(x)]; }
	std::vector<std::vector<int>> groups()
	{
		std::vector<int> rbuf(n_), grsiz(n_);
		for(int i = 0; i < n_; i++)
			grsiz[(rbuf[i] = root(i))]++;
		std::vector<std::vector<int>> res(n_);
		for(int i = 0; i < n_; i++)
			res[i].reserve(grsiz[i]);
		for(int i = 0; i < n_; i++)
			res[rbuf[i]].push_back(i);
		res.erase(remove_if(res.begin(), res.end(), [&](const std::vector<int>& v)
			{ return v.empty(); }),
			res.end());
		return res;
	}
};

#line 2 "Main.cpp"

bool is_prime(LL n)
{
	if(n<=1)return false;
	if(n==2)return true;
	if(n%2==0)return false;
	for(LL i=3;i<=(LL)sqrt(n);i+=2)
	{
		if(n!=i&&n%i==0)return false;
	}
	return true;
}

void solve()
{
	using namespace std;
	STR(s);
	int n=s.size();
	LL ans=0;
	bitfor(bit,n)
	{
		LL sm=0,cur=0;
		rep(i,n)
		{
			cur=cur*10+s[i]-'0';
			bitif(bit,i)
			{
				sm+=cur;
				cur=0;
			}
		}
		sm+=cur;
		ans+=is_prime(sm);
	}
	println(ans/2);
}

std::int32_t main()
{
	// std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout << std::fixed << std::setprecision(15);
	solve();
}