int main() {
	int test, a, b, g;
	fread(buff, 1, 14000000, stdin);
	sieve();
	test = nextint();
	while(test--) {
		a = nextint(), b = nextint();
		g = gcd(a, b);
		printf("%d\n", cntdiv(g));
	}
	return 0;
}

int main(int argc, const char * argv[]) {
    reverse();
    
    sieve(5);
    
    printf("gcd: %d\n", gcd(gcd(72, 48), 54));
    printf("lcm: %d\n", lcm(lcm(6, 8), 15));
    
    printf("%d\n", fibonacciNumber3(5));
    
    return 0;
}

int solve(ull_t n)
{
	auto primes = sieve(n);
	ull_t primes_sum = 0;
	for(auto& p : primes) {
		primes_sum += p;
	}
	printf("Sum of primes up to %llu = %llu\n", n, primes_sum);
	printf("Largest found prime: %llu\n", primes.back());
	check_result(n == 10, primes_sum == 17);
	return 0;
}

unsigned count_circular() {
	char primes[LIMIT];
	unsigned counter = 0;
	int i;
	sieve(primes, LIMIT);
	for (i = 0; i < LIMIT; ++i) {
		if (primes[i] && is_circular(primes, i)) {
			++counter;
		}
	}
	return counter;
}

main()
{
	char bitarray[BITNSLOTS(47)];
	BITSET(bitarray, 23);
	BITCLEAR(bitarray, 14);
	if(BITTEST(bitarray, 35))
		printf("yep\n");
	else	printf("nope\n");

	sieve();
	return 0;
}

int main()
{
int t;
sieve();
scanf("%d",&t);
while(t--)
{
scanf("%ld",&j);
printf("%ld\n",pos[j]);
}
return 0;
}

TEST(primes, sieve) {
  int n = 100;

  bool under_test[n];

  sieve(under_test, n);

  int i;
  for (i = 2; i < n; i++) {
    EXPECT_EQ(is_prime(i), under_test[i]);
  }
}

int main()
{
    long kase,i,n;
    sieve(112000);
    scanf("%ld",&kase);
    while(kase--)
    {
        scanf("%ld",&n);
        printf("%ld\n",d[n]);
    }
    return 0;
}

int main(){
	long n;
	int ans[10] = {0, 1, 2, 6, 12, 60};
	
	sieve();
	while ( scanf("%ld", &n) != EOF ){
		if ( n < 6 ) printf("%d\n", ans[n]);
		else printf("%I64d\n", findLCM(n));
	}
	
	return 0;
}

/// Generate primes using the segmented sieve of Eratosthenes.
/// This algorithm uses O(n log log n) operations and O(sqrt(n)) space.
/// @param limit         Sieve primes <= limit.
/// @param segment_size  Size of the sieve array in bytes.
///
void segmented_sieve(int64_t limit, int segment_size = L1D_CACHE_SIZE)
{
    int sqrt = (int) std::sqrt((double) limit);
    int64_t count = (limit < 2) ? 0 : 1;
    int64_t s = 2;
    int64_t n = 3;

    // vector used for sieving
    std::vector<char> sieve(segment_size);

    // generate small primes <= sqrt
    std::vector<char> is_prime(sqrt + 1, 1);
    for (int i = 2; i * i <= sqrt; i++)
        if (is_prime[i])
            for (int j = i * i; j <= sqrt; j += i)
                is_prime[j] = 0;

    std::vector<int> primes;
    std::vector<int> next;

    for (int64_t low = 0; low <= limit; low += segment_size)
    {
        std::fill(sieve.begin(), sieve.end(), 1);

        // current segment = interval [low, high]
        int64_t high = std::min(low + segment_size - 1, limit);

        // store small primes needed to cross off multiples
        for (; s * s <= high; s++)
        {
            if (is_prime[s])
            {
                primes.push_back((int) s);
                next.push_back((int)(s * s - low));
            }
        }
        // sieve the current segment
        for (std::size_t i = 1; i < primes.size(); i++)
        {
            int j = next[i];
            for (int k = primes[i] * 2; j < segment_size; j += k)
                sieve[j] = 0;
            next[i] = j - segment_size;
        }

        for (; n <= high; n += 2)
            if (sieve[n - low]) // n is a prime
                count++;
    }

    std::cout << count << " primes found." << std::endl;
}

// if 3k+7 is not a prime, 3k+7 = a*b, then a, b <= 3k+6, 
// we get (3k+7) | (3k+6)!, so item = 0
// if 3k+7 is prime, (3k+7) | (3k+6)!+1 by Wilson's theorem
// so item = 1
int main() {
	sieve();
	for (int i = 1; i < 1048576; i++)
		S[i] = S[i-1] + (GET(3 * i + 7) == 0);
	
	int testcase, n; 
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		printf("%d\n", S[n]);
	} 
	return 0;
}

int main() {
  constexpr long long SIZE = 5;
  std::array<long long, SIZE> curr;
  long long bound = 9999;
  long long result = bound * SIZE;

  while (result >= bound * SIZE) {
    sieve(std::max<long long>(bound * 10, 99999999));
    result = seek_seq<SIZE>(curr, 0, bound);
    bound *= 5;
  }
  std::cout << result << std::endl;
}

void top_main(int rank) {
	int primes[3];
	primes[0] = 2;
	primes[1] = 3;
	primes[2] = 5;
	printf("Hello from the top\n");
	fflush(stdout);

	int* composites = (int*)malloc(sizeof(int) * 100);
	initialize_range(composites, 100, 6);
	sieve(primes, 3, composites, 100);
	drop_ints(composites, 100);
}

int main()
{
    int t,n;
    int ans=0;
    sieve();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        ans=primeno[n]-primeno[n/2];
        printf("%d\n",ans);
    }
}

int main(int argc, char *argv[])
{
    int number = 0, i = 1;	//	number is triangle number, i is current term
    int sizeOfPrimes = 1000, sizeOfPrimesSqr = 1000000;
    int *primes;
    int numPrimes = sieve(sizeOfPrimes, &primes);

    while(numDivisors(number, primes, numPrimes) < 500) {
        if(sizeOfPrimesSqr < number) {	// Update if it becomes too small
            sizeOfPrimes *= 5;
            sizeOfPrimesSqr = sizeOfPrimes*sizeOfPrimes;
            numPrimes = sieve(sizeOfPrimes, &primes);
        }
        number += i++;					// Increment number
    }

    printf("Triangle number: %d\n", number);

    free(primes);

    return 0;
}

int main() {
    sieve();
    int l, r;
    int cases = 0;
    while (scanf("%d %d", &l, &r) == 2) {
    	int ret = 0;
    	assert(l >= 1 && l <= r);
    	for (long long i = l; i <= r; i ++)
    		ret += isPrime(i);
		printf("%d\n", ret);
	}
    return 0;
}

int main(int argc, char **argv) 
{
	pid_t pid;
	int i = 1;
	int top, floor;
	make_fifo();

	if (argc < 2)
	{
		fprintf(stderr, "usage: %s 44 100...\n", argv[0]);
		exit(1);
	}

	for(; argv[i] != '\0'; i++)
	{
		pid = fork();

		if (pid < 0)
		{
			exit(1);
		} 
		
		else if (pid == 0)
		{
			if(i == 1)
			{
				floor = 2;
			}
			else floor = atoi(argv[i-1]) + 1;
			top = atoi(argv[i]);

			printf("child %i: bottom=%i, top=%i\n", getpid(), floor, top);
			sieve(floor, top);
			exit(0x47);
		} 
		
		else
		{
			int status = 0;
			read_fifo();
			wait(&status);
			
			if(status == 18176) 
				printf("child %i exited cleanly\n", pid);
			
			else
				printf("unknown exit %i (0x%x)\n", status, status);
		}
	}
	return 0;
}

int main()
{
	int n;
	sieve(50000);
	
	while(scanf("%d",&n))
	{
		if(isprime(n))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

int main() {
	std::vector<int64_t> trunc_primes;
	
	// Generate a list of primes and check if each prime is truncatable
	euler::PrimeSieve sieve(kLimit);
	std::vector<int64_t> primes = sieve.getPrimes();
	
	for (int i = 5; trunc_primes.size() != 11 && i < primes.size(); i++)
		if (is_trunc_prime(primes[i], sieve)) trunc_primes.push_back(primes[i]);

	int64_t solution = std::accumulate(trunc_primes.begin(), trunc_primes.end(), 0);
	std::cout << solution << std::endl;
	
}

int main()
{
  sieve_of_eratosthenes<int> sieve(p_bound + 1);
  for (int i = 2; i < p_bound + 1; ++i)
    {
      if (sieve[i])
        {
          primes.push_back(i);
        }
    }
  iterate(1, 1, 0, max_first);
  std::cout << result << std::endl;
  return 0;
}