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

public class hat_nv {
	BufferedReader br;
	PrintWriter out;
	StringTokenizer stok;

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

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

	void solve() throws IOException {
		long t = nextLong();
		while (t-- > 0) {
			long n = nextLong(), k = nextLong();
			out.println(Long.bitCount(n - 1) % k);
		}
	}

	void run() throws IOException {
		br = new BufferedReader(new FileReader("hat.in"));
		out = new PrintWriter("hat.out");
		solve();
		br.close();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		Locale.setDefault(Locale.US);
		new hat_nv().run();
	}
}
