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

int main()
{
	int T;
	cin >> T;

	int N = 5000000;
	vector<bool> prime( N + 1, true );
	for( int i = 2; i <= N; i++ ) {
		if( prime[ i ] ) {
			for( int j = 2 * i; j <= N; j += i ) {
				prime[ j ] = false;
			}
		}
	}

	for( int i = 0; i < T; i++ ) {
		long long A, P;
		cin >> A >> P;
		if( prime[P] == false ) cout << -1 << endl;
		else {
			int ans = 0;
			if( A % P ) ans = 1;
			cout << ans << endl;
		}
	}
}