3760. 打工人的简单问题

The simple problem of the working class person

time limit per test: 1s

memory limit per test：256MB

Description:

The working class person has been given another task by the boss, and this time it's a simple one. The working class person gets a headache when it comes to math, so he wants you to help him solve this problem:

A prime number is a natural number greater thanthat has no divisors other than  and itself. Specifically, is not considered a prime number. Twin primes are a pair of prime numbers that differ by . In other words, if  is a prime number and  is also a prime number, then  and  are called a pair of twin primes. Now, we randomly select two numbers without replacement from the range  to . What is the probability of selecting a pair of twin primes?

Input Format:

The first line contains a positive integer , indicating the number of test cases.

Following that, there are  lines, each containing a positive integer , representing the range.

Output Format:

One integer per line, representing the value of the probability modulo .

Input Case#1

2
10
12345

Output Case#1

644444449
669805489

Input Case#2

2
10000000
1234567

Output Case#2

83016823
478474895

Note

Consider the first test case in the first set of data: (3,5),(5,7) are twin primes. Therefore, the answer is.

打工人的简单问题

时间限制:1s

内存限制：256MB

题目描述

打工人又双叒叕被老板派任务了，这次老板给了他一个简单的任务。打工人一看到数学就头疼，所以他想请你来帮他解决这个问题：

质数是指在大于  的自然数之中，除了  和其本身不再有因数的自然数。特别的, 不是质数。孪生质数是指相差为  的质数对，即如果  为质数且  也为质数，则称  和  为一对孪生质数，我们从  到  中不放回地抽取两个数，抽到孪生质数的概率是多少?

输入格式

第一行一个正整数 ，表示测试组数。

接下来  行，每行一个正整数 表示范围。

输出格式

每行一个整数，表示概率取模 后的值。

输入样例#1

2
10
12345

输出样例#1

644444449
669805489

输入样例#2

2
10000000
1234567

输出样例#2

83016823
478474895

备注

考虑第一组数据中第一个测试用例： (3,5),(5,7) 是孪生质数。所以答案为

难度等级：	0
总通过次数：	7
总提交次数：	162