// Arup Guha
// 10/15/2016
// Solution to 2015 NY Regional Problem D: Farey Sequence Length

import java.util.*;

public class d {

	public static void main(String[] args) {

		// We precalculate phi of each integer up to 10,000.
		int[] phi = new int[10001];
		for (int i=2; i<10001; i++) {
			
			// Prime factorize the number.
			ArrayList<Integer> primes = primeFact(i);

			// Then plug into the phi formula.
			phi[i] = 1;
			for (int j=0; j<primes.size(); j+=2) {
				int b = primes.get(j);
				int e = primes.get(j+1);
				phi[i] = phi[i]*(pow(b,e)-pow(b,e-1));
			}
		}

		// Make a cumulative frequency array of these, since we want the sum of the phis of each denominator.
		int[] cumfreq = new int[10001];
		cumfreq[2] = phi[2];
		for (int i=3; i<10001; i++)
			cumfreq[i] = cumfreq[i-1] + phi[i];


		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process each case - we add 2 because 1 appears as a denominator twice.
		for (int loop=0; loop<numCases; loop++) {
			int caseNum = stdin.nextInt();
			int n = stdin.nextInt();
			System.out.println(caseNum+" "+(cumfreq[n]+2));

		}
	}

	// So we don't have to deal with doubles.
	public static int pow(int b, int e) {
		int res = 1;
		for (int i=0; i<e; i++)
			res *= b;
		return res;
	}

	// Returns the primefactorization of n.
	public static ArrayList<Integer> primeFact(int n) {

		// Store pairs of numbers in this list, even indexes store bases, the next odd index stores exponents.
		ArrayList<Integer> list = new ArrayList<Integer>();
		int div = 2;
		while (div*div <= n) {

			// Divide out!
			int exp = 0;
			while (n%div == 0) {
				exp++;
				n /= div;
			}

			// Only add useful terms.
			if (exp > 0) {
				list.add(div);
				list.add(exp);
			}

			div++;
		}

		// Don't forget this case, a prime leftover!
		if (n > 1) {
			list.add(n);
			list.add(1);
		}
		return list;
	}
}