primed-position

Prime numbers are those numbers which have only 2 factors, 1 and the number itself. For example, 3 is a prime number have factors 1 and 3 only.

Now, all the prime numbers are arranged sequentially in ascending order. i.e:- 2, 3, 5,7...and so on. Now, your task is to calculate those prime numbers which are present at a prime position. For example, 2 is present at position 1 which is not a prime number while 3 is present at position 2 which is a prime  number, hence 3 is the first prime positioned number. Now, these primed positioned prime numbers are numbered is ascending order such that:

first prime positioned number is 3. So, it is given number 1.

second prime positioned number is 5. So, it is given number 2. 

and so on. Now, we are given 2 numbers n and m which denotes the nth and mth prime positioned numbers. Now, your task is to calculate the multiplication of prime positioned number present at nth and mth position. Since the answer may be large, output the answer modulo 10^9 + 7.

INPUT

First line contains an integer t denoting the number of test cases. The next t lines contains two integers n and m separated by space, denoting the prime positioned numbers which are given numbers n and m.

OUTPUT

A single integer (one per line) for each test t, that is the answer to the question.

CONSTRAINTS

1 ≤ t ≤10^6

1 ≤ n,m ≤10000

SAMPLE INPUT
2
1 2
2 3

SAMPLE OUTPUT
15 
55

Explanation

Test case 1: Here n=1 and m=2. Now, 1st and 2nd prime positioned numbers are 3 and 5 respectively. So, answer is 3*5=15.

Test case 2: Here n=2 and m=3. Now, 2nd and 3rd prime positioned numbers are 5 and 11 respectively. So, answer is 55.

Source: hackerearth | Difficulty: MEDIUM


Solutions:
N, primes = 1367000, [1,]
mod = 1000000007
check = [True]*(N+1)
check[0] = check[1] = False

for i in range(2,1+N//2):
	for j in range(2,1+N//i):
		check[i*j] = False

for i in range(2,N+1):
	if check[i]:
		primes.append(i)

for _ in range(int(input())):
	n,m = list(map(int, input().split()))
	print((primes[primes[m]]%mod * primes[primes[n]]%mod)%mod)



import sys

ar = [True for i in range(10**7+10)]
ar[0],ar[1] = False, False
for i in range(2,int((10**7+10)**0.5)):
	if ar[i] == True:
		for j in range(i**2, 10**7, i):
		   ar[j] = False

pr = []
for i in range(10**7):
	if ar[i] == True:
		pr.append(i)

fr = [0]
ln = len(pr)
for i in pr:
	if i<ln:
		fr.append(pr[i-1])
	else:
		break

for _ in range(eval(input())):
	m,n = list(map(int,sys.stdin.readline().split()))
	mod = 10**9+7
	print(fr[m]*fr[n]%mod)


'__author__'=='deepak Singh Mehta(learning Knapsack!!(dp) :) ) '

'''
	Deciding what not to do is 
	as impotant as deciding
	what to do. 
	This is a space optimized Knapsack problem.

'''

mod = 1000000007

def primes_sieve(limit):
	limitn = limit+1
	not_prime = [False] * limitn
	primes = []

	for i in range(2, limitn):
		if not_prime[i]:
			continue
		for f in range(i*2, limitn, i):
			not_prime[f] = True
		primes.append(i)

	return primes


if __name__=='__main__':
	primes = primes_sieve(10000000)
	tests = int(input())
	for _ in range(tests):
		m , n = list(map(int,input().split()))
		k1 = primes[primes[m-1]-1]
		k2 = primes[primes[n-1]-1]
		print(((k1*k2)%mod))