#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i = 0; i < n; i++)
#define Rep(i, m, n) for(long long i = m; i < n; i++)
#define REP(i, m, n, p) for(long long i = m; i < n; i += p)
#define all(v) v.begin(), v.end()
#define pq priority_queue
#define bcnt(n) __builtin_popcountll(n)

const int mod = 1000000007;
// const int mod = 998244353;
// const int mod = 1000003;

using vi = vector<int>;	 // intの1次元の型に vi という別名をつける
using vvi = vector<vi>;	 // intの2次元の型に vvi という別名をつける
using vvvi = vector<vvi>;
using ll = long long;  // long longをllだけにした
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using mii = map<int, int>;
using pqll = priority_queue<long long>;
using pqllg = priority_queue<long long, vector<long long>, greater<long long>>;
using mll = map<long long, long long>;
using pll = pair<long long, long long>;
using sll = set<long long>;
using vpll = vector<pair<long long, long long>>;
using mlv = map<long long, vector<long long>>;

long long divup(long long a, long long b);
long long kaijou(long long i);
long long P(long long n, long long k);
long long C(long long n, long long k);
long long GCD(long long a, long long b);
long long LCM(long long a, long long b);
bool prime(long long N);
double distance(vector<long long> p, vector<long long> q, long long n);
void press(vector<long long> &v);
void ranking(vector<long long> &v);
void erase(vector<long long> &v, long long i);
void unique(vector<long long> &v);
void printv(vector<long long> v);
vector<long long> keta(ll x);
long long modpow(long long a, long long n, long long mod);
long long modinv(long long a, long long mod);
// 20200416
vector<long long> inputv(long long n);
// 20200417
vector<long long> yakusuu(int n);
map<long long, long long> soinsuu(long long n);
vector<vector<long long>> maze(long long i, long long j, vector<string> &s);
// 20200423
vector<long long> eratos(long long n);
set<long long> eraset(long long n);
//////////////////////////////////////////////////////

//端数繰りあがり割り算(検証済)
// a÷bの端数繰り上げ
// b!=0のデバグはしてないので分母に0を入れないように
//負数対応
long long divup(long long a, long long b) {
	long long x = abs(a);
	long long y = abs(b);
	long long z = (x + y - 1) / y;
	if((a < 0 && b > 0) || (a > 0 && b < 0))
		return -z;
	else if(a == 0)
		return 0;
	else
		return z;
}

//階乗
//検証済み
long long kaijou(long long i) {
	if(i == 0) return 1;
	long long j = 1;
	for(long long k = 1; k <= i; k++) {
		j *= k;
	}
	return j;
}

//順列nPk(完成)
// n個の異なる要素から、取り出す順序を区別してk個取り出す場合の数
// n<kなら0を返す
//敢えて負数時のデバグはしてない
long long P(long long n, long long k) {
	if(n < k) return 0;
	long long y = 1;
	for(long long i = 0; i < k; i++) {
		y *= (n - i);
	}
	return y;
}
//組み合わせnCk(検証済み)
// P,kaijouと併用
long long C(long long n, long long k) {
	if(n < k) return 0;
	return P(n, k) / kaijou(k);
}
// nHk
//区別しないn個の要素を、区別するk個のグループに分ける
// 0個のグループがあっ
//て良い
// C必須

//最大公約数GCD,最小公倍数LCM
// LCMを使うときはGCDをセットで
//検証済み
long long GCD(long long a, long long b) {
	if(a < b) swap(a, b);
	long long d = a % b;
	if(d == 0) {
		return b;
	}
	return GCD(b, d);
}
long long LCM(long long a, long long b) { return (a / GCD(a, b)) * b; }

//素数判定
//素数ならばtrue、素数以外の整数にはfalse
//負数は全てfalse
//検証済み
bool prime(long long N) {
	if(N == 1) {
		return false;
	}
	if(N < 0) return false;
	long long p = sqrt(N);
	for(long long i = 2; i <= p; i++) {
		if(N % i == 0) {
			return false;
		}
	}
	return true;
}

//ユークリッド距離
//検証済み
//位置ベクトル1,位置ベクトル2,ベクトルの次元(2または3が一般的)
double distance(vector<long long> p, vector<long long> q, long long n) {
	double x = 0;
	for(long long i = 0; i < n; i++) {
		x += pow((p.at(i) - q.at(i)), 2);
	}
	return sqrt(x);
}

//配列圧縮(検証済)
//{1,36,1,3,8,-2,-92}を
//{2, 5,2,3,4, 1,  0}にする
void press(vector<long long> &v) {
	long long n = v.size();
	vector<long long> w(n);
	map<long long, long long> m;
	for(auto &p : v) {
		m[p] = 0;
	}
	long long i = 0;
	for(auto &p : m) {
		p.second = i;
		i++;
	}
	for(long long i = 0; i < n; i++) {
		w.at(i) = m[v.at(i)];
	}
	v = w;
	return;
}

//配列のi番目の要素がj番目に小さいとき、j番目の数がiであるベクトルを返す関数
//配列の要素が全て異なるときにしか正常に動作しない
//配列の要素に同じものが含まれても見かけ上動作はするが意味のない値を戻し、
//エラーも起きないので注意
//検証済
//{2,4,1,6,0,3,8,9,5}を
//{4,2,0,5,1,8,3,6,7}にして返す
//"rank"という名前にするとSTLの関数(配列の次元を返す関数)になるので注意
void ranking(vector<long long> &v) {
	long long n = v.size();
	map<long long, long long> m;
	long long i;
	for(i = 0; i < n; i++) {
		m[v.at(i)] = i;
	}
	vector<long long> w(n);
	i = 0;
	for(auto &p : m) {
		v.at(i) = p.second;
		i++;
	}
	return;
}

//部分削除(未検証)
//ベクトルのi番目(i=0,1,2,...,n-1)の要素を削除し、
//以降の要素を全て前に1ずらして参照返し
//ベクトル長は1小さくなって返る
// i>n-1の時は変化しない
void erase(vector<long long> &v, long long i) {
	long long n = v.size();
	if(i > n - 1) return;
	for(long long j = i; j < n - 1; j++) {
		v.at(j) = v.at(j + 1);
	}
	v.pop_back();
	return;
}

//重複削除(未完成)
//引数ベクトルに同一要素が複数あるとき、先頭を残し他は削除
//参照返し
//ベクトル長も変化する
// O(logn)くらい
void unique(vector<long long> &v) {
	long long n = v.size();
	set<long long> s;
	long long i = 0;
	while(i < n) {
		if(s.count(v.at(i))) {
			erase(v, i);
			n--;
		} else {
			s.insert(v.at(i));
			i++;
		}
	}
	return;
}

//ベクトルの出力(検証済)
// debug用にvectorの中身を出力する
void printv(vector<long long> v) {
	cout << "{ ";
	for(auto &p : v) {
		cout << p << ",";
	}
	cout << "}" << endl;
}

// 10進法でn桁の整数xに対して、大きい方の位から、その位の1桁の数字を
//収納した長さnのベクトルを返す
// 0に対しては{0}を返す
//検証済み
vector<ll> keta(ll x) {
	if(x == 0) return {0};
	ll n = log10(x) + 1;  // xの桁数
	vll w(n, 0);
	for(ll i = 0; i < n; i++) {
		ll p;
		p = x % 10;
		x = x / 10;
		w[n - 1 - i] = p;
	}
	return w;
}

// 20200415
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while(n > 0) {
		if(n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// a^{-1} mod を計算する
// modとaが互いに素のときのみ有効(数学的に逆元が一意に定まるのがそのときのみ)
long long modinv(long long a, long long mod) { return modpow(a, mod - 2, mod); }

//整数n個の入力を受け取ってベクトルに突っ込んで返す
//チェック済み
vector<long long> inputv(long long n) {
	vector<long long> v(n);
	for(long long i = 0; i < n; i++) {
		cin >> v[i];
	}
	return v;
}

vector<long long> yakusuu(long long n)	// nの約数を列挙
{
	vector<long long> ret;
	for(long long i = 1; i <= sqrt(n); ++i) {
		if(n % i == 0) {
			ret.push_back(i);
			if(i * i != n) {
				ret.push_back(n / i);
			}
		}
	}
	sort(ret.begin(), ret.end());
	return ret;
}

map<long long, long long> soinsuu(long long n) {
	map<long long, long long> m;
	long long p = sqrt(n);
	while(n % 2 == 0) {
		n /= 2;
		if(m.count(2)) {
			m[2]++;
		} else {
			m[2] = 1;
		}
	}
	for(long long i = 3; i * i <= n; i += 2) {
		while(n % i == 0) {
			n /= i;
			if(m.count(i)) {
				m[i]++;
			} else {
				m[i] = 1;
			}
		}
	}
	if(n != 1) m[n] = 1;
	return m;
}

//スタートが(i,j)の迷路の全ての地点までの距離を幅優先探索で解く
//スタートから何マス離れているか(辿り着けない場合は-1)を入れたベクトルを返す
//壁からスタートしても正常に動作するので注意(この関数の外で処理が必要)
//検証済み 一応O(地図の広さ)くらい
vector<vector<long long>> maze(ll i, ll j, vector<string> &s) {
	ll h = s.size();
	ll w = s[0].size();
	queue<vector<long long>> q;
	vector<vector<long long>> dis(h, vll(w, -1));
	q.push({i, j});
	dis[i][j] = 0;
	while(!q.empty()) {
		auto v = q.front();
		q.pop();
		if(v[0] > 0 && s[v[0] - 1][v[1]] == '.' && dis[v[0] - 1][v[1]] == -1) {
			dis[v[0] - 1][v[1]] = dis[v[0]][v[1]] + 1;
			q.push({v[0] - 1, v[1]});
		}
		if(v[1] > 0 && s[v[0]][v[1] - 1] == '.' && dis[v[0]][v[1] - 1] == -1) {
			dis[v[0]][v[1] - 1] = dis[v[0]][v[1]] + 1;
			q.push({v[0], v[1] - 1});
		}
		if(v[0] < h - 1 && s[v[0] + 1][v[1]] == '.' && dis[v[0] + 1][v[1]] == -1) {
			dis[v[0] + 1][v[1]] = dis[v[0]][v[1]] + 1;
			q.push({v[0] + 1, v[1]});
		}
		if(v[1] < w - 1 && s[v[0]][v[1] + 1] == '.' && dis[v[0]][v[1] + 1] == -1) {
			dis[v[0]][v[1] + 1] = dis[v[0]][v[1]] + 1;
			q.push({v[0], v[1] + 1});
		}
	}
	return dis;	 //スタートから何マス離れているか(辿り着けない場合は-1)
}

//エラトステネスのふるいによりn以下の素数を全てベクトルに入れて返す
// vector<long long> eratos(long long n){
// }

//二項係数の剰余を求める
//引数は剰余の形ではなくもとの数そのものである
//未検証(検証サンプルがない)
long long modC(long long n, long long k, long long mod) {
	if(n < k) return 0;
	long long p = 1, q = 1;
	for(long long i = 0; i < k; i++) {
		p = p * (n - i) % mod;
		q = q * (i + 1) % mod;
	}
	return p * modinv(q, mod) % mod;
}

// 20200418
// 整数のとき限定の普通のPOW関数
//標準機能のpow(a,n)は整数だとバグるのでこちらを使う
long long POW(long long a, long long n) {
	long long res = 1;
	while(n > 0) {
		if(n & 1) res = res * a;
		a = a * a;
		n >>= 1;
	}
	return res;
}

// 20200423
//エラトステネスのふるいによりn以下の素数を全てベクトルに入れて返す
vector<long long> eratos(long long n) {
	if(n < 2) return {};
	vll v(n - 1);
	rep(i, n - 1) {
		v[i] = i + 2;  // 2からnまで
	}
	ll i = 0;
	while(i < n - 1) {
		ll p = v[i];
		for(ll j = i + 1; j < n - 1; j++) {
			if(v[j] % p == 0) {
				v.erase(v.begin() + j);
				n--;
			}
		}
		i++;
	}
	v.resize(n - 1);
	return v;
}

// n以下の素数を全て詰めたset
set<long long> eraset(long long n) {
	set<long long> s;
	vll v = eratos(n);
	for(auto &t : v) {
		s.insert(t);
	}
	return s;
}

// 20200428
//(x1,y1),(x2,y2)を通る直線をax+by+c=0としたとき
//{a,b,c}を返す
vll line(ll x1, ll y1, ll x2, ll y2) {
	vector<ll> v(3);
	v[0] = y1 - y2;
	v[1] = x2 - x1;
	v[2] = -x1 * (y1 - y2) + y1 * (x1 - x2);
	return v;
}

//(x,y)とv[0]x+v[1]y+v[2]=0との距離
double dis(vll v, ll x, ll y) {
	double s = sqrt(v[0] * v[0] + v[1] * v[1]);
	return (double)abs(v[0] * x + v[1] * y + v[2]) / s;
}

// 20200502
void maxin(ll &a, ll b) {
	a = max(a, b);
	return;
}

void minin(ll &a, ll b) {
	a = min(a, b);
	return;
}

// 20200506
map<long long, long long> countv(vll v) {
	map<long long, long long> m;
	for(auto &g : v) {
		if(m.count(g))
			m[g]++;
		else
			m[g] = 1;
	}
	return m;
}

// nCk modを求める
const ll MAX = 510000;
// この値は求める二項計数の値に応じて変える
// MAX=3*10^7のとき1900msほど、ほぼ比例
// MAX=5*10^6程度ならそれほど気にしなくてよい(300ms程)
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void cominit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(ll i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}
// 二項係数計算
long long commod(ll n, ll k) {
	if(n < k) return 0;
	if(n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//順列計算
long long pmod(ll n, ll k) {
	if(n < k) return 0;
	if(n < 0 || k < 0) return 0;
	return fac[n] * finv[n - k] % mod;
}

/* next combination */
//次の組み合わせをbitで返す
//全探索のloopに使える
long long next_combination(long long sub) {
	long long x = sub & -sub, y = sub + x;
	return (((sub & ~y) / x) >> 1) | y;
}

// 20200617
void warshall(vector<vector<long long>> &v) {
	ll n = v.size();
	rep(i, n) {
		rep(j, n) {
			rep(k, n) {
				// cout << i << " " << j << " " << k << "\n";
				// cout << v[j][k] << " " << v[j][i] << " " << v[i][k] << "\n\n";
				v[j][k] = min(v[j][k], v[j][i] + v[i][k]);
			}
		}
	}
	return;
}

// 20200626
vvll comb(100, vll(100, -1));
long long com(long long n, long long k) {
	if(n < 0 || k < 0) return -1;
	if(n < k) return comb[n][k] = 0;
	if(comb[n][k] != -1) return comb[n][k];
	ll res;
	if(n - k < k)
		res = com(n, n - k);
	else if(k == 0)
		res = 1;
	else
		res = com(n - 1, k - 1) + com(n - 1, k);
	comb[n][k] = res;
	return res;
}

long long com2(long long n, long long k) {
	if(n < 0 || k < 0) return -1;
	if(n < k) return comb[n][k] = 0;
	ll res;
	if(n - k < k)
		res = com(n, n - k);
	else if(k == 0)
		res = 1;
	else
		res = com(n - 1, k - 1) + com(n - 1, k);
	return res;
}
void comset() { rep(i, 100) rep(j, 100) com(i, j); }

// 20200709
string bits(long long n, long long k) {
	// nをk桁のbitで表示したstringを返す
	string s = "";
	rep(i, k) {
		char c = '0' + (n % 2);
		s += c;
		n /= 2;
	}
	reverse(all(s));
	return s;
}
//////////////////////////////////////////

struct UF {						  //サイズが測れるUF
	vector<long long> par, size;  // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
	// sizeはiを根とする木のサイズ
	UF(long long N) : par(N), size(N) {	 //最初は全てが根であるとして初期化
		for(long long i = 0; i < N; i++) {
			par[i] = i;
			size[i] = 1;
		}
	}

	long long root(long long x) {  // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if(par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(long long x, long long y) {	// xとyの木を併合
		long long rx = root(x);				// xの根をrx
		long long ry = root(y);				// yの根をry
		if(rx == ry) return;				// xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry;						// xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
		size[ry] += size[rx];
		size[rx] = 0;  //サイズの処理 根じゃなくなったらサイズは0になる
	}

	bool same(long long x, long long y) {  // 2つのデータx, yが属する木が同じならtrueを返す
		long long rx = root(x);
		long long ry = root(y);
		return rx == ry;
	}
};

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division

struct mint {
	ll x;  // typedef long long ll;
	mint(ll x = 0) : x((x % mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint &operator+=(const mint a) {
		if((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator-=(const mint a) {
		if((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const { return mint(*this) += a; }
	mint operator-(const mint a) const { return mint(*this) -= a; }
	mint operator*(const mint a) const { return mint(*this) *= a; }
	mint pow(ll t) const {
		if(!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if(t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod - 2); }
	mint &operator/=(const mint a) { return *this *= a.inv(); }
	mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream &operator>>(istream &is, const mint &a) { return is >> a.x; }
ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }

void debug(ll &a) { cout << a << endl; }
void debug(vll &a) {
	cout << "debug vector" << endl;
	cout << "{ ";
	for(auto t : a) {
		cout << t << ",";
	}
	cout << " }" << endl;
	cout << "debug finished" << endl;
}
void debug(set<long long> &a) {
	cout << "debug set" << endl;
	for(auto t : a) {
		cout << t << endl;
	}
	cout << "debug finished" << endl;
}
void debug(map<long long, long long> a) {
	cout << "debug map" << endl;
	for(auto t : a) {
		cout << t.first << " " << t.second << endl;
	}
	cout << "debug finished" << endl;
}
void debug(queue<long long> a) {
	cout << "debug queue" << endl;
	while(!a.empty()) {
		ll t = a.front();
		a.pop();
		cout << t << endl;
	}
	cout << "debug finished" << endl;
}

// 20200604
struct STmax {	//最大値を測るセグ木
	ll size;	// treeの葉の数=m*2-1
	ll m;		// tree最下段の数
	vector<long long> seg;
	STmax(long long n) : size(n), m(n), seg(0) {
		m = 1;
		while(m < n) {
			m *= 2;
		}
		size = m * 2 - 1;
		rep(i, size) { seg.push_back(-99999999977); }
	}

	//ここまで共通
	// minの場合はpush_backの値をdekaiにする？

	void update(ll i, ll k) {  // i番目をkに更新
		ll v = i + m - 1;
		seg[v] = k;
		while(v > 0) {
			v = (v - 1) / 2;
			seg[v] = max(seg[v * 2 + 1], seg[v * 2 + 2]);
		}
	}
	ll query(ll a, ll b, ll k, ll l, ll r) {  //区間[a,b)での最大値を求める
		if(r <= a || b <= l) return -99999999977;
		if(a <= l && r <= b) return seg[k];
		// cout << "#" << a << " " << b << " " << k << " " << l << " " << r << endl;
		ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return max(vl, vr);
	}
	ll largest(ll a, ll b) {
		if(a >= b) return -99999999977;
		return query(a, b, 0, 0, m);
	}
};

struct STmin {	//最小値を測るセグ木
	ll size;	// treeの葉の数=m*2-1
	ll m;		// tree最下段の数
	vector<long long> seg;
	STmin(long long n) : size(n), m(n), seg(0) {
		m = 1;
		while(m < n) {
			m *= 2;
		}
		size = m * 2 - 1;
		rep(i, size) { seg.push_back(99999999977); }
	}

	//ここまで共通
	// minの場合はpush_backの値をdekaiにする？

	void update(ll i, ll k) {  // i番目をkに更新
		ll v = i + m - 1;
		seg[v] = k;
		while(v > 0) {
			v = (v - 1) / 2;
			seg[v] = min(seg[v * 2 + 1], seg[v * 2 + 2]);
		}
	}
	ll query(ll a, ll b, ll k, ll l, ll r) {  //区間[a,b)での最大値を求める
		if(r <= a || b <= l) return 99999999977;
		if(a <= l && r <= b) return seg[k];
		// cout << "#" << a << " " << b << " " << k << " " << l << " " << r << endl;
		ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
	ll smallest(ll a, ll b) {
		if(a >= b) return 99999999977;
		return query(a, b, 0, 0, m);
	}
};

struct STsum {	//区間の合計値を測るセグ木
	ll size;	// treeの葉の数=m*2-1
	ll m;		// tree最下段の数
	vector<long long> seg;
	STsum(long long n) : size(n), m(n), seg(0) {
		m = 1;
		while(m < n) {
			m *= 2;
		}
		size = m * 2 - 1;

		rep(i, size) { seg.push_back(0); }
		//改造時はここをまず変える
	}

	//ここまで共通
	// minの場合はpush_backの値をdekaiにする

	void update(ll i, ll k) {  // i番目をkに更新
		ll v = i + m - 1;
		seg[v] = k;
		while(v > 0) {
			v = (v - 1) / 2;

			seg[v] = seg[v * 2 + 1] + seg[v * 2 + 2];
			//改造時はここを変える
		}
	}
	ll query(ll a, ll b, ll k, ll l, ll r) {  //区間[a,b)での最大値を求める
		if(r <= a || b <= l) return 0;
		if(a <= l && r <= b) return seg[k];
		// cout << "#" << a << " " << b << " " << k << " " << l << " " << r << endl;
		ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);

		return vl + vr;	 //改造時はここを変える
	}
	ll sum(ll a, ll b) {
		if(a >= b) return 0;
		return query(a, b, 0, 0, m);
	}
};
//////////////////////////////////////////////

// // 多倍長テンプレ
// /* ---------------------- ここから ---------------------- */
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// // 任意長整数型
// using Bint = mp::cpp_int;
// // 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
// using Real = mp::number<mp::cpp_dec_float<1024>>;
// /* ---------------------- ここまで ---------------------- */

// ll const mod=1e9+7;
ll const dekai = 9223372036854775807;  // POW(2,63)-1.素数.
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, -1, 0, 1};
ll ddx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
ll ddy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// cout<<fixed<<setprecision(10);
#define ednl endl
#define endk endl
#define enld endl
//////////////////////////////////////////////////
using ld = long double;

// vvll ruiseki(vvll v, ll h, ll w) {
// 	vvll res(h + 1, vll(w + 1, 0));
// 	rep(i, h) {
// 		rep(j, w) { res[i + 1][j + 1] = v[i][j]; }
// 	}
// 	rep(i, h + 1) {
// 		rep(j, w) { res[i][j + 1] += res[i][j]; }
// 	}
// 	rep(i, h) {
// 		rep(j, w + 1) { res[i + 1][j] += res[i][j]; }
// 	}
// 	return res;
// }

// //{x,y},{x+dx,y},{x,y+dy},{x+dx,y+dy}の区画の合計を求める
// long long sheetsum(ll x, ll y, ll dx, ll dy, vvll &v) { return v[x + dx][y + dy] - v[x + dx][y] - v[x][y + dy] + v[x][y]; }

int main() {
	int t;
	cin >> t;
	ll h = 5000000;
	vll v(h + 1, 1);
	v[0] = v[1] = 0;
	ll i = 2;
	while(i < h) {
		if(v[i] == 1) {
			ll k = 2;
			while(i * k <= h) {
				v[i * k] = 0;
				k++;
			}
		}
		i++;
	}
	vll ans(t);
	rep(i, t) {
		ll a, p;
		cin >> a >> p;
		if(v[p] == 0) {
			ans[i] = -1;
		} else {
			if(a % p == 0)
				ans[i] = 0;
			else
				ans[i] = 1;
		}
	}
	rep(i, t) { cout << ans[i] << endl; }
}