#include <bits/stdc++.h>
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/04/15  Problem: yukicoder 061  / Link: http://yukicoder.me/problems/no/061  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */
//const int base = 1000000000; //blockの幅
//const int base_digits = 9; //
//
//struct BigInt {
//	vector<int> a;
//	int sign;
//
//	BigInt() :
//		sign(1) {
//	}
//
//	BigInt(long long v) {
//		*this = v;
//	}
//
//	BigInt(const string &s) {
//		read(s);
//	}
//
//	void operator=(const BigInt &v) {
//		sign = v.sign;
//		a = v.a;
//	}
//
//	void operator=(long long v) {
//		sign = 1;
//		if (v < 0)
//			sign = -1, v = -v;
//		a.clear();
//		for (; v > 0; v = v / base)
//			a.push_back(v % base);
//	}
//
//	BigInt operator+(const BigInt &v) const {
//		if (sign == v.sign) {
//			BigInt res = v;
//
//			for (int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry; ++i) {
//				if (i == (int)res.a.size())
//					res.a.push_back(0);
//				res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
//				carry = res.a[i] >= base;
//				if (carry)
//					res.a[i] -= base;
//			}
//			return res;
//		}
//		return *this - (-v);
//	}
//
//	BigInt operator-(const BigInt &v) const {
//		if (sign == v.sign) {
//			if (abs() >= v.abs()) {
//				BigInt res = *this;
//				for (int i = 0, carry = 0; i < (int)v.a.size() || carry; ++i) {
//					res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
//					carry = res.a[i] < 0;
//					if (carry)
//						res.a[i] += base;
//				}
//				res.trim();
//				return res;
//			}
//			return -(v - *this);
//		}
//		return *this + (-v);
//	}
//
//	void operator*=(int v) {
//		if (v < 0)
//			sign = -sign, v = -v;
//		for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i) {
//			if (i == (int)a.size())
//				a.push_back(0);
//			long long cur = a[i] * (long long)v + carry;
//			carry = (int)(cur / base);
//			a[i] = (int)(cur % base);
//			//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
//		}
//		trim();
//	}
//
//	BigInt operator*(int v) const {
//		BigInt res = *this;
//		res *= v;
//		return res;
//	}
//
//	friend pair<BigInt, BigInt> divmod(const BigInt &a1, const BigInt &b1) {
//		int norm = base / (b1.a.back() + 1);
//		BigInt a = a1.abs() * norm;
//		BigInt b = b1.abs() * norm;
//		BigInt q, r;
//		q.a.resize(a.a.size());
//
//		for (int i = a.a.size() - 1; i >= 0; i--) {
//			r *= base;
//			r += a.a[i];
//			int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
//			int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
//			int d = ((long long)base * s1 + s2) / b.a.back();
//			r -= b * d;
//			while (r < 0)
//				r += b, --d;
//			q.a[i] = d;
//		}
//
//		q.sign = a1.sign * b1.sign;
//		r.sign = a1.sign;
//		q.trim();
//		r.trim();
//		return make_pair(q, r / norm);
//	}
//
//	friend BigInt sqrt(const BigInt &a1) {
//		BigInt a = a1;
//		while (a.a.empty() || a.a.size() % 2 == 1)
//			a.a.push_back(0);
//
//		int n = a.a.size();
//
//		int firstDigit = (int)sqrt((double)a.a[n - 1] * base + a.a[n - 2]);
//		int norm = base / (firstDigit + 1);
//		a *= norm;
//		a *= norm;
//		while (a.a.empty() || a.a.size() % 2 == 1)
//			a.a.push_back(0);
//
//		BigInt r = (long long)a.a[n - 1] * base + a.a[n - 2];
//		firstDigit = (int)sqrt((double)a.a[n - 1] * base + a.a[n - 2]);
//		int q = firstDigit;
//		BigInt res;
//
//		for (int j = n / 2 - 1; j >= 0; j--) {
//			for (; ; --q) {
//				BigInt r1 = (r - (res * 2 * base + q) * q) * base * base + (j > 0 ? (long long)a.a[2 * j - 1] * base + a.a[2 * j - 2] : 0);
//				if (r1 >= 0) {
//					r = r1;
//					break;
//				}
//			}
//			res *= base;
//			res += q;
//
//			if (j > 0) {
//				int d1 = res.a.size() + 2 < r.a.size() ? r.a[res.a.size() + 2] : 0;
//				int d2 = res.a.size() + 1 < r.a.size() ? r.a[res.a.size() + 1] : 0;
//				int d3 = res.a.size() < r.a.size() ? r.a[res.a.size()] : 0;
//				q = ((long long)d1 * base * base + (long long)d2 * base + d3) / (firstDigit * 2);
//			}
//		}
//
//		res.trim();
//		return res / norm;
//	}
//
//	BigInt operator/(const BigInt &v) const {
//		return divmod(*this, v).first;
//	}
//
//	BigInt operator%(const BigInt &v) const {
//		return divmod(*this, v).second;
//	}
//
//	void operator/=(int v) {
//		if (v < 0)
//			sign = -sign, v = -v;
//		for (int i = (int)a.size() - 1, rem = 0; i >= 0; --i) {
//			long long cur = a[i] + rem * (long long)base;
//			a[i] = (int)(cur / v);
//			rem = (int)(cur % v);
//		}
//		trim();
//	}
//
//	BigInt operator/(int v) const {
//		BigInt res = *this;
//		res /= v;
//		return res;
//	}
//
//	int operator%(int v) const {
//		if (v < 0)
//			v = -v;
//		int m = 0;
//		for (int i = a.size() - 1; i >= 0; --i)
//			m = (a[i] + m * (long long)base) % v;
//		return m * sign;
//	}
//
//	void operator+=(const BigInt &v) {
//		*this = *this + v;
//	}
//	void operator-=(const BigInt &v) {
//		*this = *this - v;
//	}
//	void operator*=(const BigInt &v) {
//		*this = *this * v;
//	}
//	void operator/=(const BigInt &v) {
//		*this = *this / v;
//	}
//
//	bool operator<(const BigInt &v) const {
//		if (sign != v.sign)
//			return sign < v.sign;
//		if (a.size() != v.a.size())
//			return a.size() * sign < v.a.size() * v.sign;
//		for (int i = a.size() - 1; i >= 0; i--)
//			if (a[i] != v.a[i])
//				return a[i] * sign < v.a[i] * sign;
//		return false;
//	}
//
//	bool operator>(const BigInt &v) const {
//		return v < *this;
//	}
//	bool operator<=(const BigInt &v) const {
//		return !(v < *this);
//	}
//	bool operator>=(const BigInt &v) const {
//		return !(*this < v);
//	}
//	bool operator==(const BigInt &v) const {
//		return !(*this < v) && !(v < *this);
//	}
//	bool operator!=(const BigInt &v) const {
//		return *this < v || v < *this;
//	}
//
//	void trim() {
//		while (!a.empty() && !a.back())
//			a.pop_back();
//		if (a.empty())
//			sign = 1;
//	}
//
//	bool isZero() const {
//		return a.empty() || (a.size() == 1 && !a[0]);
//	}
//
//	BigInt operator-() const {
//		BigInt res = *this;
//		res.sign = -sign;
//		return res;
//	}
//
//	BigInt abs() const {
//		BigInt res = *this;
//		res.sign *= res.sign;
//		return res;
//	}
//
//	long long longValue() const {
//		long long res = 0;
//		for (int i = a.size() - 1; i >= 0; i--)
//			res = res * base + a[i];
//		return res * sign;
//	}
//
//	friend BigInt gcd(const BigInt &a, const BigInt &b) {
//		return b.isZero() ? a : gcd(b, a % b);
//	}
//	friend BigInt lcm(const BigInt &a, const BigInt &b) {
//		return a / gcd(a, b) * b;
//	}
//
//	void read(const string &s) {
//		sign = 1;
//		a.clear();
//		int pos = 0;
//		while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) {
//			if (s[pos] == '-')
//				sign = -sign;
//			++pos;
//		}
//		for (int i = s.size() - 1; i >= pos; i -= base_digits) {
//			int x = 0;
//			for (int j = max(pos, i - base_digits + 1); j <= i; j++)
//				x = x * 10 + s[j] - '0';
//			a.push_back(x);
//		}
//		trim();
//	}
//
//	friend istream& operator>>(istream &stream, BigInt &v) {
//		string s;
//		stream >> s;
//		v.read(s);
//		return stream;
//	}
//
//	friend ostream& operator<<(ostream &stream, const BigInt &v) {
//		if (v.sign == -1 && !v.isZero())
//			stream << '-';
//		stream << (v.a.empty() ? 0 : v.a.back());
//		for (int i = (int)v.a.size() - 2; i >= 0; --i)
//			stream << setw(base_digits) << setfill('0') << v.a[i];
//		return stream;
//	}
//
//	static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
//		vector<long long> p(max(old_digits, new_digits) + 1);
//		p[0] = 1;
//		for (int i = 1; i < (int)p.size(); i++)
//			p[i] = p[i - 1] * 10;
//		vector<int> res;
//		long long cur = 0;
//		int cur_digits = 0;
//		for (int i = 0; i < (int)a.size(); i++) {
//			cur += a[i] * p[cur_digits];
//			cur_digits += old_digits;
//			while (cur_digits >= new_digits) {
//				res.push_back(int(cur % p[new_digits]));
//				cur /= p[new_digits];
//				cur_digits -= new_digits;
//			}
//		}
//		res.push_back((int)cur);
//		while (!res.empty() && !res.back())
//			res.pop_back();
//		return res;
//	}
//
//	typedef vector<long long> vll;
//
//	static vll karatsubaMultiply(const vll &a, const vll &b) {
//		int n = a.size();
//		vll res(n + n);
//		if (n <= 32) {
//			for (int i = 0; i < n; i++)
//				for (int j = 0; j < n; j++)
//					res[i + j] += a[i] * b[j];
//			return res;
//		}
//
//		int k = n >> 1;
//		vll a1(a.begin(), a.begin() + k);
//		vll a2(a.begin() + k, a.end());
//		vll b1(b.begin(), b.begin() + k);
//		vll b2(b.begin() + k, b.end());
//
//		vll a1b1 = karatsubaMultiply(a1, b1);
//		vll a2b2 = karatsubaMultiply(a2, b2);
//
//		for (int i = 0; i < k; i++)
//			a2[i] += a1[i];
//		for (int i = 0; i < k; i++)
//			b2[i] += b1[i];
//
//		vll r = karatsubaMultiply(a2, b2);
//		for (int i = 0; i < (int)a1b1.size(); i++)
//			r[i] -= a1b1[i];
//		for (int i = 0; i < (int)a2b2.size(); i++)
//			r[i] -= a2b2[i];
//
//		for (int i = 0; i < (int)r.size(); i++)
//			res[i + k] += r[i];
//		for (int i = 0; i < (int)a1b1.size(); i++)
//			res[i] += a1b1[i];
//		for (int i = 0; i < (int)a2b2.size(); i++)
//			res[i + n] += a2b2[i];
//		return res;
//	}
//
//	BigInt operator*(const BigInt &v) const {
//		vector<int> a6 = convert_base(this->a, base_digits, 6);
//		vector<int> b6 = convert_base(v.a, base_digits, 6);
//		vll a(a6.begin(), a6.end());
//		vll b(b6.begin(), b6.end());
//		while (a.size() < b.size())
//			a.push_back(0);
//		while (b.size() < a.size())
//			b.push_back(0);
//		while (a.size() & (a.size() - 1))
//			a.push_back(0), b.push_back(0);
//		vll c = karatsubaMultiply(a, b);
//		BigInt res;
//		res.sign = sign * v.sign;
//		for (int i = 0, carry = 0; i < (int)c.size(); i++) {
//			long long cur = c[i] + carry;
//			res.a.push_back((int)(cur % 1000000));
//			carry = (int)(cur / 1000000);
//		}
//		res.a = convert_base(res.a, 6, base_digits);
//		res.trim();
//		return res;
//	}
//
//	friend BigInt pow(const BigInt &x, BigInt a) {
//		BigInt res = 1;
//		BigInt e = x;
//		for (; !a.isZero(); a /= BigInt(2)) {
//			if (a % 2 == 1) {
//				res *= e;
//			}
//			e *= e;
//		}
//		return res;
//	}
//	friend BigInt powmod(const BigInt &x, BigInt a, const BigInt &mod) {
//		BigInt X = x%mod;
//		BigInt res = 1;
//		BigInt e = X;
//		for (; !a.isZero(); a /= BigInt(2)) {
//			if (a % 2 == 1) {
//				res = (res*e) % mod;
//			}
//			e = (e*e) % mod;
//		}
//		return res%mod;
//	}
//
//
//	// 拡張ユークリッド互除法 a*x+b*y=1となる整数解x,yを求める
//	// 返却値: gcd(a,b)
//	friend BigInt extgcd(BigInt a, BigInt b, BigInt &x, BigInt &y) {
//		BigInt gcd_ = a;
//		if (b != 0) {
//			gcd_ = extgcd(b, a%b, y, x);
//			y -= (a / b)*x;
//		}
//		else {
//			x = 1; y = 0;
//		}
//		return gcd_;
//	}
//
//};
struct BigInt {
public:
	using LL = long long int;
	static const LL BASE = 1000000000;
	const int DIG = 9;

	bool neg;
	std::vector<LL> dig;

	BigInt() : neg(false), dig(1, 0ll) {}
	BigInt(const char* str) : BigInt(std::string(str)) {}
	BigInt(const std::string& str) : neg(false) {
		if (str.empty()) {
			dig.assign(1, 0);
			return;
		}

		int b = 0;
		if (str[b] == '-') {
			neg = true;
			++b;
		}

		LL crt = 0;
		LL p = 1;
		for (int i = (int)(str.size()) - 1; i >= b; --i, p *= 10) {
			if (p == BASE) {
				dig.emplace_back(crt);
				crt = 0;
				p = 1;
			}
			if (!isdigit(str[i])) {
				throw "Non digit is given.";
			}
			crt += p * (str[i] - '0');
		}
		dig.emplace_back(crt);
		norm();
	}
	BigInt(LL x) : neg(x < 0), dig(1, std::abs(x)) {
		for (unsigned int i = 0; i < dig.size(); ++i) {
			if (dig[i] >= BASE) {
				dig.emplace_back(dig[i] / BASE);
				dig[i] %= BASE;
			}
		}
	}
	BigInt& operator=(const BigInt& rhs) {
		neg = rhs.neg;
		dig = rhs.dig;
		return *this;
	}
	BigInt& operator=(LL x) { return *this = BigInt(x); }
	BigInt& operator=(const char* s) { return *this = BigInt(s); }
	BigInt& operator=(const std::string& s) { return *this = BigInt(s); }

	bool iszero() const {
		return dig.size() == 1 && dig[0] == 0;
	}

	BigInt operator-() const {
		BigInt res = *this;
		if (!res.iszero())
			res.neg = !res.neg;
		return res;
	}

	//! ignoring sign
	static int comp(const BigInt& l, const BigInt& r) {
		if (l.dig.size() != r.dig.size())
			return (l.dig.size() < r.dig.size() ? -1 : 1);

		for (int i = (int)(l.dig.size()) - 1; i >= 0; --i) {
			if (l.dig[i] != r.dig[i])
				return (l.dig[i] < r.dig[i] ? -1 : 1);
		}
		return 0;
	}
	//! add ignoring sign
	static void add(BigInt& l, const BigInt& rhs) {
		unsigned int i;
		for (i = 0; i < rhs.dig.size(); ++i) {
			if (l.dig.size() <= i) {
				l.dig.emplace_back(rhs.dig[i]);
			}
			else {
				l.dig[i] += rhs.dig[i];
				if (l.dig[i] >= BASE) {
					l.dig[i] -= BASE;
					if (l.dig.size() <= i + 1)
						l.dig.emplace_back(0);
					l.dig[i + 1]++;
				}
				else if (l.dig[i] < 0) {
					l.dig[i] += BASE;
					if (l.dig.size() <= i + 1)
						l.dig.emplace_back(0);
					l.dig[i + 1]--;
				}
			}
		}
		for (; i < l.dig.size(); ++i)
			if (l.dig[i] >= BASE) {
				l.dig[i] -= BASE;
				if (l.dig.size() <= i + 1)
					l.dig.emplace_back(0);
				l.dig[i + 1]++;
			}
	}
	// subtract ignoring sign, supposed to l >= rhs
	static void sub(BigInt& l, const BigInt& rhs) {
		unsigned int i;
		for (i = 0; i < rhs.dig.size(); ++i) {
			l.dig[i] -= rhs.dig[i];
			if (l.dig[i] < 0) {
				l.dig[i] += BASE;
				l.dig[i + 1]--;
			}
		}
		for (; i < l.dig.size(); ++i)
			if (l.dig[i] < 0) {
				l.dig[i] += BASE;
				l.dig[i + 1]--;
			}
	}

	void flip() {
		for (unsigned int i = 0; i < dig.size(); ++i)
			dig[i] *= -1;
	}
	void norm() {
		while (dig.size() > 1 && dig.back() == 0) dig.pop_back();
		if (iszero()) neg = false;
	}
	bool operator==(const BigInt& rhs) const {
		if (neg != rhs.neg || dig.size() != rhs.dig.size()) return false;
		return comp(*this, rhs) == 0;
	}
	bool operator<(const BigInt& rhs) const {
		if (neg != rhs.neg) return neg ? true : false;
		if (neg) return comp(rhs, *this) == -1;
		return comp(*this, rhs) == -1;
	}
	bool operator<=(const BigInt& rhs) const {
		if (neg != rhs.neg) return neg ? true : false;
		if (neg) return comp(rhs, *this) <= 0;
		return comp(*this, rhs) <= 0;
	}
	bool operator!=(const BigInt& rhs) const { return !(*this == rhs); }
	bool operator>(const BigInt& rhs)  const { return rhs < *this; }
	bool operator>=(const BigInt& rhs) const { return rhs <= *this; }

	// ignoring sign
	void incl() {
		for (unsigned int i = 0; i < dig.size(); ++i)
			if (++dig[i] == BASE) {
				dig[i] = 0;
				if (i + 1 == dig.size()) {
					dig.push_back(1);
					break;
				}
			}
			else break;
	}
	// ignoring sign
	void decl() {
		if (iszero()) {
			dig[0] = 1;
			neg = true;
			return;
		}
		for (unsigned int i = 0; i < dig.size(); ++i)
			if (--dig[i] == -1)
				dig[i] = BASE - 1;
			else break;
			norm();
	}
	BigInt& operator++() {
		if (!neg) incl(); else decl();
		return *this;
	}
	BigInt operator++(int) {
		BigInt res = *this;
		if (!neg) incl(); else decl();
		return res;
	}
	BigInt& operator--() {
		if (!neg) decl(); else incl();
		return *this;
	}
	BigInt operator--(int) {
		BigInt res = *this;
		if (!neg) decl(); else incl();
		return res;
	}

	BigInt& operator+=(const BigInt& rhs) {
		if (!this->neg) {
			if (!rhs.neg)
				add(*this, rhs);
			else {
				if (comp(*this, rhs) >= 0)
					sub(*this, rhs);
				else {
					flip();
					add(*this, rhs);
					neg = true;
				}
			}
		}
		else {
			if (!rhs.neg) {
				if (comp(rhs, *this) >= 0) {
					flip();
					add(*this, rhs);
					neg = false;
				}
				else
					sub(*this, rhs);
			}
			else
				add(*this, rhs);
		}

		norm();
		return *this;
	}
	BigInt& operator-=(const BigInt& rhs) { return *this += -rhs; }
	BigInt operator+(const BigInt& rhs) const { BigInt res = *this; return res += rhs; }
	BigInt operator-(const BigInt& rhs) const { BigInt res = *this; return res -= rhs; }
	BigInt operator*(const BigInt& rhs) const {
		BigInt res;
		res.dig.assign(dig.size() + rhs.dig.size() + 1, 0ll);
		res.neg = neg ^ rhs.neg;

		for (unsigned i = 0; i < rhs.dig.size(); ++i) {
			if (rhs.dig[i] == 0) continue;
			for (unsigned j = 0; j < dig.size(); ++j) {
				res.dig[i + j] += rhs.dig[i] * dig[j];
				if (res.dig[i + j] >= BASE) {
					res.dig[i + j + 1] += res.dig[i + j] / BASE;
					res.dig[i + j] %= BASE;
				}
			}
		}
		res.norm();

		return res;
	}
	BigInt operator*=(const BigInt& rhs) { return *this = *this * rhs; }

	static void divll(BigInt& x, LL& r, LL d) {
		bool lneg = x.neg;
		x.neg ^= (d < 0);
		if (d < 0) d *= -1;

		r = 0;
		for (int i = (int)x.dig.size() - 1; i >= 0; --i) {
			r = r * BASE + x.dig[i];
			x.dig[i] = r / d;
			r %= d;
		}
		x.norm();

		if (r != 0 && lneg)
			r *= -1;
	}

	void powB(LL x) {
		if (iszero()) return;
		while (x > 0) {
			dig.insert(dig.begin(), 0ll);
			--x;
		}
	}
	static void divmod(BigInt& q, BigInt& r, const BigInt& lhs, const BigInt& rhs) {
		int cmp = comp(lhs, rhs);
		if (cmp < 0) {
			q.dig = std::vector<LL>(1, 0ll);
			q.neg = false;
			r = lhs;
			return;
		}
		else if (cmp == 0) {
			q.dig = std::vector<LL>(1, 1ll);
			q.neg = false;
			r.dig = std::vector<LL>(1, 0ll);
			r.neg = false;
			return;
		}
		if (rhs.dig.size() == 1) {
			LL rl;
			q = lhs;
			divll(q, rl, rhs.dig[0] * (rhs.neg ? -1ll : 1ll));
			r = rl;
			return;
		}

		q.neg = r.neg = false;

		int u = lhs.dig.size() - rhs.dig.size() + 1;
		q.dig.assign(u + 1, 0ll);

		LL K = BASE / (rhs.dig.back() + 1);
		BigInt ltmp = lhs, rtmp = rhs;
		ltmp.neg = rtmp.neg = false;

		if (K > 1) {
			ltmp *= K;
			rtmp *= K;
		}

		LL x = ltmp.dig.back() / rtmp.dig.back();
		if (x == 0) {
			--u;
			x = (ltmp.dig.back() * BASE + ltmp.dig[ltmp.dig.size() - 2]) / rtmp.dig.back();
		}
		BigInt w = 0ll;
		while (true) {
			w = rtmp;
			w.powB(u);
			if (comp(w, ltmp) > 0) {
				--u;
				continue;
			}
			while (true) {
				w = rtmp * x;
				w.powB(u);
				if (comp(w, ltmp) <= 0) break;
				--x;
			}

			q.dig[u--] = x;
			ltmp -= w;
			if (ltmp == 0ll || u < 0) break;

			x = std::min(BASE - 1,
				(ltmp.dig.back() * BASE + ltmp.dig[ltmp.dig.size() - 2]) / rtmp.dig.back());
		}
		q.norm();

		r = ltmp;
		if (ltmp != 0ll) divll(r, x, K);
		q.neg = lhs.neg ^ rhs.neg;
		r.neg = lhs.neg;
		r.norm();
	}

	BigInt operator/(const BigInt& rhs) const {
		BigInt q, r;
		divmod(q, r, *this, rhs);
		return q;
	}
	BigInt operator%(const BigInt& rhs) const {
		BigInt q, r;
		divmod(q, r, *this, rhs);
		return r;
	}
	BigInt& operator/=(BigInt rhs) { return *this = *this / rhs; }
	BigInt& operator%=(BigInt rhs) { return *this = *this % rhs; }

	std::string to_string() const {
		assert(!dig.empty());
		std::string res = neg ? "-" : "";

		std::ostringstream os;
		os << std::to_string(dig.back());
		for (int i = (int)(dig.size()) - 2; i >= 0; --i) {
			os << std::setfill('0') << std::setw(DIG) << dig[i];
		}
		res += os.str();
		return res;
	}
	// convert long long int anyway
	LL to_ll() const {
		LL res = 0, p = 1;
		for (unsigned int i = 0; i < dig.size(); ++i) {
			res += dig[i] * p;
			p *= BASE;
		}
		return res * (neg ? -1ll : 1);
	}


};

int xx = 0;
BigInt zero(xx);

BigInt gcd(const BigInt &a, const BigInt &b) {
	return b == zero ? a : gcd(b, a % b);
}
// 拡張ユークリッド互除法 a*x+b*y=1となる整数解x,yを求める
// 返却値: gcd(a,b)
BigInt extgcd(BigInt a, BigInt b, BigInt &x, BigInt &y) {
	BigInt gcd_ = a;
	if (!b.iszero()) {
		gcd_ = extgcd(b, a%b, y, x);
		y -= (a / b)*x;
	}
	else {
		x = 1; y = zero;
	}
	return gcd_;
}
std::ostream& operator<<(std::ostream& os, const BigInt& x) { return os << x.to_string(); }

BigInt W, H, D, Mx, My, Hx, Hy, Vx, Vy;


int f(BigInt tx, BigInt ty) {
	BigInt A = W * 2 * Vy;
	BigInt B = -H * 2 * Vx;
	BigInt C = ty*Vx - tx*Vy + Hx*Vy - Hy*Vx;
	BigInt g = gcd(A, -B);

	if (!(C % g).iszero()) {
		return 0;
	}
	A /= g; B /= g; C /= g;
	BigInt x, y;
	g = extgcd(B, A, y, x);
	if (g < zero) {
		g *= -1; y *= -1; x *= -1;
	}
	BigInt m = C*y%A;
	BigInt tv = (ty + H*m * 2 - Hy) / Vy;
	tv = tv % (H * 2 * A / Vy);
	if (tv < zero)tv += H * 2 * A / Vy;
	return (tv <= D);
}
string w, h, d, mx, my, hx, hy, vx, vy;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int Q; cin >> Q;
	FOR(q, 0, Q) {
		cin >> w >> h >> d >> mx >> my >> hx >> hy >> vx >> vy;
		W = w, H = h, D = d, Mx = mx, My = my, Hx = hx, Hy = hy, Vx = vx, Vy = vy;
		if (Vx < zero) {
			Mx = W - Mx;
			Hx = W - Hx;
			Vx = -Vx;
		}
		if (Vy < zero) {
			My = H - My;
			Hy = H - Hy;
			Vy = -Vy;
		}

		int res = 0;
		if (Vx == zero) {
			if (Mx == Hx && ((My > Hy && My - Hy <= D*Vy) || (My < Hy && H * 2 - My - Hy <= D*Vy))) {
				res = 1;
			}
			else {
				res = -1;
			}
		}
		else if (Vy == zero) {
			if (My == Hy && ((Mx > Hx && Mx - Hx <= D*Vx) || (Mx < Hx && W * 2 - Mx - Hx <= D*Vx))) {
				res = 1;
			}
			else {
				res = -1;
			}
		}
		if (res) {
			if (res == 1)printf("Hit\n");
			else printf("Miss\n");
		}
		else {
			BigInt g = gcd(Vx, Vy);
			D *= g;
			Vx /= g, Vy /= g;
			if (f(Mx, My) || f(W * 2 - Mx, My) || f(Mx, H * 2 - My) || f(W * 2 - Mx, H * 2 - My)) {
				res = 1;
			}
			if (res == 1)printf("Hit\n");
			else printf("Miss\n");
		}

	}

	return 0;
}