#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<string>
#include<math.h>
#include<map>
#include<set>
#include<string.h>
#include<iomanip>
#include<queue>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
//int mod = 998244353;


int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		ull p, m;
		cin >> p >> m;
		ull k = 0,ans=0;
		for (k = 0;k*p+1<=m ; k++)
		{
			if (((k * p + 1) ^ (p - 1)) <= m)
			{
				ans++;
			}
		}
		cout << ans << endl;
	}
}