7224: gcd problem
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
Given a positive integer N, output how many pairs of (x,y) satisfy condition gcd(x,y)=k (1<=x,y<=N , k is a prime).
输入
The first line contains an integer t (1<=t<=100) — the number of test cases.
Then next t lines contains a positive integer N (1<=N<=10^6)
It is guaranteed that the sum of the values of N over all test cases does not exceed 10^8
Then next t lines contains a positive integer N (1<=N<=10^6)
It is guaranteed that the sum of the values of N over all test cases does not exceed 10^8
输出
For each test case,output the answer on a single line.
样例输入 复制
1
4样例输出 复制
4提示
gcd(2,2)=gcd(2,4)=gcd(4,2)=2 , gcd(3,3)=3 , so the answer is 4.