import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static final String IN_FILE = "pinex.in";
  public static final String OUT_FILE = "pinex.out";

  private static final int MAX_PRIME = 1_000_000;
  private static final int[] PRIMES = getPrimesLessThan(MAX_PRIME + 1);

  private static int[] getPrimesLessThan(final int maxValue) {
    final boolean[] isComposite = new boolean[maxValue];
    final List<Integer> primes = new ArrayList<Integer>();
    primes.add(2);
    for (int i = 3; i < maxValue; i += 2) {
      if (isComposite[i]) {
        continue;
      }
      primes.add(i);
      for (int j = (int) Math.min(maxValue, 1L * i * i); j < maxValue; j += i) {
        isComposite[j] = true;
      }
    }
    return primes.stream().mapToInt(Integer::intValue).toArray();
  }

  public static long[] factorize(final long n) {
    long current = n;
    final List<Long> factors = new ArrayList<>();
    for (int prime : PRIMES) {
      if (1L * prime * prime > n) {
        break;
      }
      if (current % prime == 0) {
        factors.add((long) prime);
        for (; current % prime == 0; current /= prime) ;
      }
    }
    if (current > 1) {
      factors.add(current);
    }
    return factors.stream().mapToLong(Long::longValue).toArray();
  }

  public static class Solver {
    private final long maxValue;
    private final long[] factors;
    private final long coprimeCount;

    public Solver(final long maxValue, final long coprimeValue) {
      this.maxValue = maxValue;
      this.factors = factorize(coprimeValue);
      this.coprimeCount = count(1L, 0, 1);
    }

    public long getCoprimeCount() {
      return coprimeCount;
    }

    private long count(final long value, final int i, final int sign) {
      if (i == factors.length) {
        return sign * maxValue / value;
      }
      return count(value, i + 1, sign)
          + count(value * factors[i], i + 1, -sign);
    }
  }

  public static void main(final String[] args) throws IOException {
    try (final Scanner scanner = new Scanner(new FileInputStream(IN_FILE));
        final PrintStream writer = new PrintStream(OUT_FILE)) {
      final int tests = scanner.nextInt();
      for (int t = 1; t <= tests; t++) {
        final long maxValue = scanner.nextLong();
        final long coprimeValue = scanner.nextLong();
        final long coprimeCount = new Solver(maxValue, coprimeValue)
            .getCoprimeCount();
        writer.println(coprimeCount);
      }
    }
  }
}