import java.io.*;
import java.util.*;

public class hat_va_nextInt {
	public static void main(String[] args) {
		new hat_va_nextInt().run();
	}

	BufferedReader br;
	StringTokenizer in;
	PrintWriter out;

	public String nextToken() throws IOException {
		while (in == null || !in.hasMoreTokens()) {
			in = new StringTokenizer(br.readLine());
		}
		return in.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public void solve() throws IOException {
		int n = nextInt();
		int p = nextInt();

		long[] pow = new long[61];
		pow[0] = 1;
		for (int i = 1; i < pow.length; i++) {
			pow[i] = 2 * pow[i - 1];
		}

		n--;
		int ans = 0;
		for (int i = pow.length - 1; i >= 0; i--) {
			if (n >= pow[i]) {
				n -= pow[i];
				ans++;
			}
		}
		out.println(ans % p);
	}

	public void run() {
		try {
			br = new BufferedReader(new FileReader("hat.in"));
			out = new PrintWriter("hat.out");

			int t = nextInt();
			for (int i = 0; i < t; i++)
				solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}
