import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		PrintWriter pw = new PrintWriter(System.out);
		for (int z = 0; z < t; z++) {
			String[] sa = br.readLine().split(" ");
			char[] n = sa[0].toCharArray();
			int m = Integer.parseInt(sa[1]);
			int m2 = m * 2;

			long v1 = 0;
			for (int i = 0; i < n.length; i++) {
				v1 *= 10;
				v1 += n[i] - '0';
				v1 %= m2;
			}
			long ans = v1 * (v1 + 1) / 2 % m;
			pw.println(ans);
		}
		pw.flush();
		br.close();
	}
}