#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
#define N 105
#define max(a, b)  (((a) > (b)) ? (a) : (b))
int main()
{
	int t, a, b, p, ans = 1, book[N], k = 0, flag = 0;
	freopen("drei.in", "r", stdin);
	freopen("drei.out", "w", stdout);

	scanf("%d", &t);
	
	while(t--)
	{

		scanf("%d %d", &a, &p);
		
		if(a % 2 == 0&&p % 2 == 0)
		{
			flag = 1;
		}
		if(a % 2 == 1&&p % 2 == 1)
		{
			flag = 1;
		}
		if(p == 1)
		{
			flag = 1;
		}
		if(flag)
		{

			printf("-1\n");

			flag = 0;
			continue;
		}
		b = a;
		while(b % p != 1)
		{
			b %= p;
			b *= a;
			ans++;
		}

		printf("%d\n", ans);
		ans = 1;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}