#line 1 "code.cpp"
/*#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")//*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#line 2 "/home/wa_haya_exe/CP_Library/C++/template.hpp"
#ifndef TEMPLATE
#define TEMPLATE
#endif
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wdeprecated-copy"
#include <bits/stdc++.h>
namespace VvyLw {
enum TestCase { single, multi };
inline void solve() noexcept;
template <TestCase tc = single, int x = 12> constexpr inline void wa_haya_exe() noexcept {
	std::cin.tie(nullptr) -> sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(x);
	int t = 1;
	if constexpr (tc == multi) {
		std::cin >> t;
	}
	for([[maybe_unused]] const auto _: std::views::iota(0, t)) {
		solve();
	}
}
}

using enum VvyLw::TestCase;

#line 2 "/home/wa_haya_exe/CP_Library/C++/core/alias.hpp"

#ifndef ALIAS
#define ALIAS
#endif

#line 8 "/home/wa_haya_exe/CP_Library/C++/core/alias.hpp"
#include <numbers>
#line 10 "/home/wa_haya_exe/CP_Library/C++/core/alias.hpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

namespace internal {
template <typename T> concept num = std::integral<T> || std::floating_point<T>;
}

constexpr int dx[] = {0, 0, 0, -1, 1, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, -1, 1, -1, 1};
constexpr int MOD = 0x3b800001;
constexpr int M0D = 1e9 + 7;
constexpr int INF = 1 << 30;
constexpr int64_t LINF = (1LL << 61) - 1;
constexpr long double DINF = std::numeric_limits<long double>::infinity();
template <internal::num T> constexpr T LIM = std::numeric_limits<T>::max();
constexpr long double PI = std::numbers::pi;
constexpr long double E = std::numbers::e;

typedef int64_t i64;
typedef long double ld;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
#ifdef MODINT
typedef man::Modint<MOD> mint;
typedef man::Modint<M0D> Mint;
#endif
template <size_t N> using ti = std::array<i64, N>;
typedef ti<3> tri;
template <class T> using pq = std::priority_queue<T>;
template <class T> using pqr = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T> using Tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <class T> using TREE = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::greater<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

/**
 * @brief エイリアス
 */
#line 28 "/home/wa_haya_exe/CP_Library/C++/template.hpp"

namespace man {
inline bool isdigit(const std::string &s) noexcept;
std::mt19937 EhaL(std::hash<std::string>()("Huitloxopetl"));
inline std::mt19937 rand() noexcept {
	std::random_device seed_gen;
	std::mt19937 engine {seed_gen()};
	return engine;
}

template <class T, class U> constexpr inline bool chmax(T& a, const U& b) noexcept { if(a < b){ a = b; return true; } return false; }
template <class T, class U> constexpr inline bool chmin(T& a, const U& b) noexcept { if(a > b){ a = b; return true; } return false; }
template <internal::num T, internal::num U> constexpr inline bool overflow_if_add(const T a, const U b) noexcept { return (std::numeric_limits<T>::max() - a) < b; }
template <internal::num T, internal::num U> constexpr inline bool overflow_if_mul(const T a, const U b) noexcept { return (std::numeric_limits<T>::max() / a) < b; }

inline std::string string_replace(const std::string &s, const std::string &a, const std::string &b) noexcept { return std::regex_replace(s, std::regex(a), b); }
inline bool regex_contains(const std::string &s, const std::string &t) noexcept { return std::regex_search(s, std::regex(t)); }
constexpr inline auto yes(const bool ok) noexcept { return ok ? "Yes" : "No"; }
template <internal::num T> constexpr inline T sqr(const T x) noexcept { return x * x; }
template <internal::num T> constexpr inline T cub(const T x) noexcept { return x * x * x; }
template <std::integral T> constexpr inline T mod(T x, const T m) noexcept {
	x %= m;
	return x < 0 ? x + m : x;
}
template <std::integral T> constexpr inline T pow(T a, T b, const T mod = 0) noexcept {
	T ret = 1;
	if(mod != 0) {
		ret %= mod;
		a %= mod;
	}
	while(b > 0) {
		if(b & 1) {
			ret *= a;
		}
		if(mod != 0) {
			ret %= mod;
		}
		a *= a;
		if(mod) {
			a %= mod;
		}
		b >>= 1;
	}
	return ret;
}
constexpr inline int64_t ceil(const long double x, const int64_t m) noexcept { return std::ceil(x / m); }
constexpr inline long double round(const long double x, const int64_t m, const short fx = 0) noexcept {
	if(fx == 0) {
		return std::round(x / m);
	}
	const uint64_t y = pow<uint64_t>(10, fx);
	return std::round((x * y) / m) / y;
}
constexpr inline long double log(const int64_t x, const long double base = 2) noexcept { return std::log2(x) / std::log2(base); }
constexpr inline int bitdigit(const int64_t x) noexcept { return 64 - __builtin_clzll(x); }
constexpr inline int popcnt(const int64_t x) noexcept { return __builtin_popcountll(x); }
constexpr inline int fione(const int64_t x) noexcept { return __builtin_ffsll(x); }
constexpr inline int zrcnt(const int64_t x) noexcept { return __builtin_ctzll(x); }
template <internal::num T> constexpr inline bool scope(const T a, const T x, const T b) noexcept { return a <= x && x <= b; }
constexpr inline bool isupper(const char c) noexcept { return std::isupper(c); }
inline bool isupper(const std::string &s) noexcept {
	bool ok = true;
	for(const auto &el: s) {
		ok &= isupper(el);
	}
	return ok;
}
constexpr inline bool islower(const char c) noexcept { return std::islower(c); }
inline bool islower(const std::string &s) noexcept {
	bool ok = true;
	for(const auto &el: s) {
		ok &= islower(el);
	}
	return ok;
}
constexpr inline bool isalpha(const char c) noexcept { return std::isalpha(c); }
inline bool isalpha(const std::string &s) noexcept {
	bool ok = true;
	for(const auto &el: s) {
		ok &= isalpha(el);
	}
	return ok;
}
constexpr inline bool isdigit(const char c) noexcept { return std::isdigit(c); }
inline bool isdigit(const std::string &s) noexcept {
	bool ok = true, neg = s.front() == '-';
    for(const auto &el: s) {
        if(neg) {
            neg = false;
            continue;
        }
        ok &= isdigit(el);
    }
    return ok;
}
constexpr inline bool isalnum(const char c) noexcept { return std::isalnum(c); }
inline bool isalnum(const std::string &s) noexcept {
	bool ok = true;
	for(const auto &el: s) {
		ok &= isalnum(el);
	}
	return ok;
}
constexpr inline bool isspace(const char c) noexcept { return std::isspace(c); }
inline bool isspace(const std::string &s) noexcept {
	bool ok = true;
	for(const auto &el: s) {
		ok &= isspace(el);
	}
	return ok;
}
constexpr inline bool ispunct(const char c) noexcept { return std::ispunct(c); }
inline bool ispunct(const std::string &s) noexcept {
	bool ok = true;
	for(const auto &el: s) {
		ok &= ispunct(el);
	}
	return ok;
}
constexpr inline bool isprint(const char c) noexcept { return std::isprint(c); }
inline bool isprint(const std::string &s) noexcept {
	bool ok = true;
	for(const auto &el: s) {
		ok &= isprint(el);
	}
	return ok;
}
inline auto strins(std::string &s, const int id, const std::string &t) noexcept {
	s.insert(id, t);
	return std::ssize(s);
}
inline std::string toupper(std::string s) noexcept {
	for(auto &c: s) {
		c = std::toupper(c);
	}
	return s;
}
inline std::string tolower(std::string s) noexcept {
	for(auto &c: s) {
		c = std::tolower(c);
	}
	return s;
}
inline std::string ten_to(int64_t n, const int base, const bool upper = true) noexcept {
	assert(base <= 10 || base == 16);
	if(base == 16) {
		std::stringstream ss;
		ss << std::hex << n;
		const std::string s = ss.str();
		return upper ? toupper(s) : s;
	}
	if(n == 0 || base == 0) {
		return "0";
	}
	std::vector<int> ret;
	while(n > 0) {
		ret.emplace_back(n % base);
		n /= base;
	}
	std::string s;
	for(const auto &e: ret | std::views::reverse) {
		s += std::to_string(e);
	}
	return s;
}
inline int64_t to_ten(const std::string &s, const int base = 10) noexcept { return std::stoll(s, nullptr, base); }
template <std::integral... Ts> constexpr uint64_t gcd(const Ts... a) noexcept {
	std::vector v = std::initializer_list<std::common_type_t<Ts...>>{a...};
	uint64_t g = 0;
	for(const auto &el: v) {
		g = std::gcd(g, el);
	}
	return g;
}
template <std::integral... Ts> constexpr uint64_t lcm(const Ts... a) noexcept {
	std::vector v = std::initializer_list<std::common_type_t<Ts...>>{a...};
	uint64_t l = 1;
	for(const auto &el: v) {
		l = std::lcm(l, el);
	}
	return l;
}
template <internal::num... Ts> constexpr auto min(const Ts... a) noexcept { return std::min(std::initializer_list<std::common_type_t<Ts...>>{a...}); }
template <internal::num... Ts> constexpr auto max(const Ts... a) noexcept { return std::max(std::initializer_list<std::common_type_t<Ts...>>{a...}); }
template <class K, class V> inline std::vector<K> key_l(const std::map<K, V> &m, const V val) noexcept {
	std::vector<K> keys;
	for(auto it = m.cbegin(); it != m.cend(); ++it) {
		if(it->second == val) {
			keys.emplace_back(it->first);
		}
	}
	return keys;
}
template <class K, class V> constexpr inline K key_min(const std::map<K, V> &m) noexcept { return m.begin()->first; }
template <class K, class V> constexpr inline K key_max(const std::map<K, V> &m) noexcept { return m.rbegin()->first; }
template <class K, class V> constexpr inline V key_min_v(const std::map<K, V> &m) noexcept { return m.begin()->second; }
template <class K, class V> constexpr inline V key_max_v(const std::map<K, V> &m) noexcept { return m.rbegin()->second; }
template <class K, class V> constexpr inline auto val_min(const std::map<K, V> &m) noexcept {
	return *std::ranges::min_element(m, [](const std::pair<K, V> &x, const std::pair<K, V> &y) -> bool { return x.second < y.second; });
}
template <class K, class V> constexpr inline auto val_max(const std::map<K, V> &m) noexcept {
	return *std::ranges::max_element(m, [](const std::pair<K, V> &x, const std::pair<K, V> &y) -> bool { return x.second < y.second; });
}

template <std::integral T> constexpr inline T count(std::vector<T> v, const T &x) noexcept {
	if(!std::ranges::is_sorted(v)) {
		std::ranges::sort(v);
	}
	return std::ranges::upper_bound(v, x) - std::ranges::lower_bound(v, x);
}
template <class T> constexpr inline T inner_prod(const std::vector<T> &v, const std::vector<T> &u, const T init) noexcept { return std::inner_product(v.cbegin(), v.cend(), u.cbegin(), init); }
inline std::vector<int> iota(const int n, const int init = 0) noexcept {
	std::vector<int> a(n);
	std::iota(a.begin(), a.end(), init);
	return a;
}
template <class T> constexpr inline int uniq(T& v) noexcept {
	if(!std::ranges::is_sorted(v)) {
		std::ranges::sort(v);
	}
	const auto it = std::ranges::unique(v);
	v.erase(it.begin(), it.end());
	return std::ssize(v);
}
template <class T> constexpr inline void rotate(T& s, const int idx) noexcept {
	const int id = mod<int>(idx, std::ssize(s));
	std::ranges::rotate(s, s.begin() + id);
}
template <class T> constexpr inline T set_diff(const T& s, const T& t) noexcept {
	assert(std::ranges::is_sorted(s) && std::ranges::is_sorted(t));
	T ret;
	std::ranges::set_difference(s, t, std::inserter(ret, std::end(ret)));
	return ret;
}
template <class T> constexpr inline T set_sum(const T& s, const T& t) noexcept {
	assert(std::ranges::is_sorted(s) && std::ranges::is_sorted(t));
	T ret;
	std::ranges::set_union(s, t, std::inserter(ret, std::end(ret)));
	return ret;
}
template <class T> constexpr inline T set_mul(const T& s, const T& t) noexcept {
	assert(std::ranges::is_sorted(s) && std::ranges::is_sorted(t));
	T ret;
	std::ranges::set_intersection(s, t, std::inserter(ret, std::end(ret)));
	return ret;
}
template <class T> inline std::vector<T> adj_diff(const std::vector<T> &v) noexcept {
	std::vector<T> a;
	std::adjacent_difference(v.cbegin(), v.cend(), std::back_inserter(a));
	rotate(a, 1);
	a.pop_back();
	return a;
}
template <class T, class F> inline std::vector<T> isum(const std::vector<T> &v, const F &fn) noexcept {
	std::vector<T> s{0};
	std::inclusive_scan(v.cbegin(), v.cend(), std::back_inserter(s), fn);
	return s;
}
template <class T> inline std::vector<T> rand_extract(const std::vector<T> &v, const int size) noexcept {
	std::vector<T> ret;
	std::ranges::sample(v, std::back_inserter(ret), size, rand());
	return ret;
}
template <class T> inline T rand_extract(const std::vector<T> &v) noexcept {
	std::vector<T> ret;
	std::ranges::sample(v, std::back_inserter(ret), 1, rand());
	return ret.front();
}
template <std::ranges::random_access_range T> inline auto sum(const T &v) noexcept { return std::accumulate(v.cbegin(), v.cend(), decltype(v.front())(0)); }
template <std::ranges::random_access_range T> inline auto sum(const T &v, const int a, const int b) noexcept { return std::accumulate(v.cbegin() + a, v.cbegin() + b, decltype(v.front())(0)); }
template <std::ranges::random_access_range T, class Boolean = bool> inline auto sum(const T &v, const Boolean &fn) noexcept { return std::accumulate(v.cbegin(), v.cend(), decltype(v.front())(0), fn); }
template <std::ranges::random_access_range T, class Boolean = bool> inline auto sum(const T &v, const int a, const int b, const Boolean &fn) noexcept { return std::accumulate(v.cbegin() + a, v.cbegin() + b, decltype(v.front())(0), fn); }

template <internal::num T, class Boolean = bool> constexpr inline T bins(T ok, T ng, const Boolean &fn, const long double eps = 1) noexcept {
	while(std::abs(ok - ng) > eps) {
		const T mid = (ok + ng) / 2;
		(fn(mid) ? ok : ng) = mid;
	}
	return ok;
}
inline std::vector<std::string> rotate(const std::vector<std::string> &s) noexcept {
	const int h = std::ssize(s), w = std::ssize(s.front());
	std::vector t(w, std::string(h, {}));
	for(const auto i: std::views::iota(0, h)) {
		for(const auto j: std::views::iota(0, w)) {
			t[j][i] = s[i][j];
		}
	}
	for(const auto i: std::views::iota(0, w)) {
		std::ranges::reverse(t[i]);
	}
	return t;
}
template <internal::num T> inline std::vector<std::vector<T>> rotate(const std::vector<std::vector<T>> &v) noexcept {
	const int h = std::ssize(v), w = std::ssize(v.front());
	std::vector ret(w, std::vector<T>(h));
	for(const auto i: std::views::iota(0, h)) {
		for(const auto j: std::views::iota(0, w)) {
			ret[j][i] = v[i][j];
		}
	}
	for(const auto i: std::views::iota(0, w)) {
		std::ranges::reverse(ret[i]);
	}
	return ret;
}
template <std::integral T> constexpr inline T factor(T n, const T mod = 0) noexcept {
	T ret = 1;
	while(n > 0) {
		ret *= n--;
		if(mod) {
			ret %= mod;
		}
	}
	return ret;
}
template <std::integral T> constexpr inline T perm(T n, const T r, const T mod = 0) noexcept {
	const T tmp = n;
	T ret = 1;
	while(n > tmp - r) {
		ret *= n--;
		if(mod) {
			ret %= mod;
		}
	}
	return ret;
}
template <std::integral T> constexpr inline T binom(T n, const T r, const T mod = 0) noexcept {
	if(r < 0 || n < r) {
		return 0;
	}
	T ret = 1;
	for(const auto i: std::views::iota(1) | std::views::take(r)) {
		ret *= n--;
		if(mod) {
			ret %= mod;
		}
		ret /= i;
		if(mod) {
			ret %= mod;
		}
	}
	return ret;
}
constexpr inline bool is_int(const long double n) noexcept { return n == std::floor(n); }
constexpr inline bool is_sqr(const int64_t n) noexcept { return is_int(std::sqrt(n)); }
}

#line 2 "/home/wa_haya_exe/CP_Library/C++/core/timer.hpp"

#line 5 "/home/wa_haya_exe/CP_Library/C++/core/timer.hpp"
using Timer = std::chrono::system_clock::time_point;
Timer start, stop;
#if local
inline void now(Timer &t) noexcept { t = std::chrono::system_clock::now(); }
inline void time(const Timer &t1, const Timer &t2) noexcept { std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() << "ms\n"; }
#else
void now(Timer &t){ void(0); }
void time(const Timer &t1, const Timer &t2){ void(0); }
#endif

/**
 * @brief タイマー
 */
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/myvector.hpp"

#line 4 "/home/wa_haya_exe/CP_Library/C++/core/myvector.hpp"

#ifndef ALIAS
namespace internal {
template <typename T> concept num = std::integral<T> || std::floating_point<T>;
}
#endif

namespace man {
namespace vec {
template <class T> using V = std::vector<T>;
typedef V<int64_t> zhl;
typedef V<uint64_t> uzhl;
typedef V<long double> dec;
typedef V<char> chr;
typedef V<std::string> str;
typedef V<bool> bol;
typedef V<zhl> zhl2;
typedef V<uzhl> uzhl2;
typedef V<dec> dec2;
typedef V<chr> chr2;
typedef V<str> str2;
typedef V<bol> bol2;
#ifdef EDGE
typedef V<man::edge> edg;
typedef V<edg> edg2;
#endif
template <class T, class U> inline V<U> ndiv(T&& n, U&& v) noexcept {
  return V<U>(std::forward<T>(n), std::forward<U>(v));
}
template <class T, class... Ts> inline decltype(auto) ndiv(T&& n, Ts&&... v) noexcept {
  return V<decltype(ndiv(std::forward<Ts>(v)...))>(std::forward<T>(n), ndiv(std::forward<Ts>(v)...));
}
template <internal::num T> constexpr V<T>& operator++(V<T>& v) noexcept { for(auto &el: v){ el++; } return v; }
template <internal::num T> constexpr V<T>& operator--(V<T>& v) noexcept { for(auto &el: v){ el--; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator+=(V<T>& v, const U x) noexcept { for(auto &el: v){ el += x; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator-=(V<T>& v, const U x) noexcept { for(auto &el: v){ el -= x; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator*=(V<T>& v, const U x) noexcept { for(auto &el: v){ el *= x; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator/=(V<T>& v, const U x) noexcept { for(auto &el: v){ el /= x; } return v; }
template <std::integral T, std::integral U> constexpr V<T>& operator%=(V<T>& v, const U x) noexcept { for(auto &el: v){ el %= x; } return v; }
template <internal::num T, internal::num U> constexpr V<T> operator+(const V<T>& v, const U x) noexcept { V<T> ret = v; ret += x; return ret; }
template <internal::num T, internal::num U> constexpr V<T> operator-(const V<T>& v, const U x) noexcept { V<T> ret = v; ret -= x; return ret; }
template <internal::num T, internal::num U> constexpr V<T> operator*(const V<T>& v, const U x) noexcept { V<T> ret = v; ret *= x; return ret; }
template <internal::num T, internal::num U> constexpr V<T> operator/(const V<T>& v, const U x) noexcept { V<T> ret = v; ret /= x; return ret; }
template <std::integral T, std::integral U> constexpr V<T> operator%(const V<T>& v, const U x) noexcept { V<T> ret = v; ret %= x; return ret; }
}
}
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/mypair.hpp"

#line 8 "/home/wa_haya_exe/CP_Library/C++/core/mypair.hpp"

#ifndef ALIAS
namespace internal {
template <typename T> concept num = std::integral<T> || std::floating_point<T>;
}
#endif

namespace man {
namespace pav {
template <class T, class U> using P = std::pair<T, U>;
template <class T> using PP = P<T, T>;
typedef PP<int64_t> zhl;
typedef PP<long double> dec;
typedef PP<char> chr;
typedef PP<std::string> str;
template <internal::num T> constexpr PP<T> operator+(const PP<T>& a, const PP<T>& b) noexcept { return {a.first + b.first, a.second + b.second}; }
template <internal::num T> constexpr PP<T> operator-(const PP<T>& a, const PP<T>& b) noexcept { return {a.first - b.first, a.second - b.second}; }
template <internal::num T> constexpr PP<T> operator-(const PP<T>& a) noexcept { return {-a.first, -a.second}; }
template <internal::num T, class U> constexpr PP<T> operator*(const PP<T>& a, const U& b) noexcept { return {a.first * b, a.second * b}; }
template <internal::num T, class U> constexpr PP<T> operator/(const PP<T>& a, const U& b) noexcept { return {a.first / b, a.second / b}; }
template <internal::num T> constexpr PP<T>& operator+=(PP<T>& a, const PP<T>& b) noexcept { return a = a + b; }
template <internal::num T> constexpr PP<T>& operator-=(PP<T>& a, const PP<T>& b) noexcept { return a = a - b; }
template <internal::num T, internal::num U> constexpr PP<T>& operator*=(PP<T>& a, const U& b) noexcept { return a = a * b; }
template <internal::num T, internal::num U> PP<T>& operator/=(PP<T>& a, const U& b) noexcept { return a = a / b; }
template <class T> constexpr bool operator==(const PP<T> &p, const PP<T> &q) noexcept { return p.first == q.first && p.second == q.second; }
template <class T> constexpr bool operator!=(const PP<T> &p, const PP<T> &q) noexcept { return !(p == q); }
template <class T> constexpr bool operator<(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second < q.second; } return p.first < q.first; }
template <class T> constexpr bool operator<=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second <= q.second; } return p.first < q.first; }
template <class T> constexpr bool operator>(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second > q.second; } return p.first > q.first; }
template <class T> constexpr bool operator>=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second >= q.second; } return p.first > q.first; }
template <class T, class U> constexpr bool operator==(const P<T, U> &p, const P<T, U> &q) noexcept { return p.first == q.first && p.second == q.second; }
template <class T, class U> constexpr bool operator!=(const P<T, U> &p, const P<T, U> &q) noexcept { return !(p == q); }
template <class T, class U> constexpr bool operator<(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second < q.second; } return p.first < q.first; }
template <class T, class U> constexpr bool operator<=(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second <= q.second; } return p.first < q.first; }
template <class T, class U> constexpr bool operator>(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second > q.second; } return p.first > q.first; }
template <class T, class U> constexpr bool operator>=(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second >= q.second; } return p.first > q.first; }
template <internal::num T> constexpr inline PP<T> rotate(const PP<T>& a) noexcept { return {-a.second, a.first}; } // 90 degree ccw
template <internal::num T> constexpr inline dec rotate(const PP<T>& a, const int ang) noexcept {
    assert(0 <= ang && ang < 360);
    const long double rad = PI * ang / 180;
    return {a.first * std::cos(rad) - a.second * std::sin(rad), a.first * std::sin(rad) + a.second * std::cos(rad)};
}
template <internal::num T> constexpr inline T dot(const PP<T>& a, const PP<T>& b) noexcept { return a.first * b.first + a.second * b.second; }
template <internal::num T> constexpr inline T cross(const PP<T>& a, const PP<T>& b) noexcept { return dot(rotate(a), b); }
template <internal::num T> constexpr inline T square(const PP<T>& a) noexcept { return dot(a, a); }
template <internal::num T> constexpr inline long double grad(const PP<T>& a) noexcept { assert(a.first != 0); return 1.0L * a.second / a.first; }
template <internal::num T> constexpr inline long double abs(const PP<T>& a) noexcept { return std::hypotl(a.first, a.second); }
template <std::integral T> constexpr inline T lcm(const PP<T>& a) noexcept { return std::lcm(a.first, a.second); }
template <std::integral T> constexpr inline T gcd(const PP<T>& a) noexcept { return std::gcd(a.first, a.second); }
template <std::integral T> constexpr inline PP<T> extgcd(const PP<T> &p) noexcept {
    T x = 1, y = 0, t1 = 0, t2 = 0, t3 = 1, a, b;
    std::tie(a,b) = p;
    while(b > 0) {
        t1 = a / b, a -= t1 * b;
        std::swap(a, b);
        x -= t1 * t2;
        std::swap(x, t2);
        y -= t1 * t3;
        std::swap(y, t3);
    }
    return {x, y};
}
template <std::integral T> constexpr inline PP<T> normalize(PP<T> a) noexcept {
    if(a == PP<T>{}) {
        return a;
    }
    a /= gcd(a);
    if(a < PP<T>{}) {
        a = -a;
    }
    return a;
}
template <class T, class U> constexpr inline P<U, T> swap(const P<T, U> &p) noexcept { const P<U, T> ret = {p.second, p.first}; return ret; }
template <class T, class U> inline std::vector<P<U, T>> swap(const std::vector<P<T, U>> &vp) noexcept {
    std::vector<P<U, T>> ret;
    for(const auto &el: vp) {
        ret.emplace_back(swap(el));
    }
    return ret;
}
template <class T, class U> inline std::vector<T> first(const std::vector<P<T, U>> &vp) noexcept {
    std::vector<T> ret;
    for(const auto &el: vp) {
        ret.emplace_back(el.first);
    }
    return ret;
}
template <class T, class U> inline std::vector<U> second(const std::vector<P<T, U>> &vp) noexcept {
    std::vector<U> ret;
    for(const auto &el: vp) {
        ret.emplace_back(el.second);
    }
    return ret;
}
}
}
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/io/input.hpp"

#line 8 "/home/wa_haya_exe/CP_Library/C++/core/io/input.hpp"
#ifndef TEMPLATE
namespace man {
constexpr inline bool isdigit(const char c) noexcept { return std::isdigit(c); }
inline bool isdigit(const std::string &s) noexcept {
    bool ok = true, neg = s.front() == '-';
    for(const auto &el: s) {
        if(neg) {
            neg = false;
            continue;
        }
        ok &= isdigit(el);
    }
    return ok;
}
}
#endif
namespace IO {
inline std::istream& operator>>(std::istream &is, __int128_t &val) noexcept {
    std::string s;
    std::cin >> s;
    assert(man::isdigit(s));
    bool neg = s.front() == '-';
    val = 0;
    for(const auto &el: s) {
        if(neg) {
            neg = false;
            continue;
        }
        val = 10 * val + el - '0';
    }
    if(s.front()=='-') {
        val = -val;
    }
    return is;
}
template <class T, class U> inline std::istream& operator>>(std::istream &is, std::pair<T, U> &p) noexcept { is >> p.first >> p.second; return is; }
template <std::ranges::random_access_range T> requires (!std::same_as<std::remove_cvref_t<T>, std::string> && !std::same_as<std::remove_cvref_t<T>, std::string_view> && !std::is_array_v<std::remove_cvref_t<T>>) inline std::istream& operator>>(std::istream &is, T &v) noexcept { for(auto &el: v){ is >> el; } return is; }
template <class Head, class... Tail> inline bool input(Head &head, Tail &...tail) noexcept {
    if(!(std::cin >> head)) {
        return false;
    }
    if constexpr(sizeof...(Tail) > 0) {
        input(tail...);
    }
    return true;
}
} // IO

/**
 * @brief 入力
 */
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/io/output.hpp"

#line 6 "/home/wa_haya_exe/CP_Library/C++/core/io/output.hpp"
namespace IO {
inline std::ostream &operator<<(std::ostream &dest, const __int128_t &value) noexcept {
    std::ostream::sentry s(dest);
    constexpr char dig[] = "0123456789";
    if(s) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = std::end(buffer);
        do {
            --d;
            *d = dig[tmp % 10];
            tmp /= 10;
        } while(tmp != 0);
        if(value < 0) {
            --d;
            *d = '-';
        }
        const int len = std::end(buffer) - d;
        if(dest.rdbuf() -> sputn(d, len) != len) {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}
template <class T, class U> inline std::ostream& operator<<(std::ostream &os, const std::pair<T, U> &p) noexcept { os << p.first << ' ' << p.second; return os; }
template <class K, class V> inline std::ostream& operator<<(std::ostream &os, const std::map<K, V> &m) noexcept {
    if(!m.empty()) {
        os << m.begin()->first << ' ' << m.begin()->second;
        for(auto i = m.begin(); ++i != m.end();) {
            os << '\n' << i->first << ' ' << i->second;
        }
    }
    return os;
}
template <std::ranges::range T> requires (!std::same_as<std::remove_cvref_t<T>, std::string> && !std::same_as<std::remove_cvref_t<T>, std::string_view> && !std::is_array_v<std::remove_cvref_t<T>>) inline std::ostream& operator<<(std::ostream &os, const T &v) noexcept {
    if(!v.empty()) {
        os << *v.cbegin();
        for(auto i = v.cbegin(); ++i != v.cend();) {
            os << ' ' << *i;
        }
    }
    return os;
}
enum Flash { non_flush, flush };
template <Flash f = non_flush, class Head, class... Tail> inline void print(const Head& head, const Tail& ...tail) noexcept {
    std::cout << head;
    if constexpr(sizeof...(Tail) > 0) {
        std::cout << ' ';
        print<f>(tail...);
    } else {
        if constexpr(f == flush) {
            std::cout.flush();
        }
    }
}
inline void println() noexcept { std::cout << '\n'; }
template <Flash f = non_flush, class Head, class... Tail> inline void println(const Head& head, const Tail& ...tail) noexcept { print<f>(head, tail...); std::cout << '\n'; }
} // IO

using enum IO::Flash;

#if local
//https://gist.github.com/naskya/1e5e5cd269cfe16a76988378a60e2ca3
#include <C++/core/io/debug_print.hpp>
#else
#define dump(...) static_cast<void>(0)
#endif

/**
 * @brief 出力
 */
#line 381 "/home/wa_haya_exe/CP_Library/C++/template.hpp"

#define REP(n) for([[maybe_unused]] const auto _: std::views::iota(0, (n)))

using namespace IO;
using namespace std::views;
namespace iter = std::ranges;

/**
 * @brief テンプレート
 * @docs docs/template.md
 */
#line 5 "code.cpp"

int main() {
	now(start);
	VvyLw::wa_haya_exe();
	now(stop);
	time(start, stop);
}

// --------------------------------------------------------------------------------------------------------------


inline void VvyLw::solve() noexcept {
	i64 d;
	input(d);
	println(d * 108 / 100.0L);
}