NAJPWG - Playing with GCD
题意翻译
$T$ 组数据，每组给定整数 $n$，求有多少对 $(i,j)$ 满足 $1 \leqslant i \leqslant j \leqslant n$ 且 $\gcd(i,j)>1$
$1 \le n \le 10^5,T \le 10^5$
题目描述
Tanmoy recently learn about euclid gcd algorithm.
This algorithm looks like:
gcd(a,b):
if(b==0):return a
return gcd(b,a%b)
Now he want to find out how many pair (x,y) can be possible in range N, which gcd is greater than 1. Here pair (x,y) and (y,x) consider as same pair. 1<=x,y<=N.
He can find out it small number easily but for a large number its realy hard to find out. Now he needs your help. Write a programme that find out number of such pair.
**Input:**
Input start with an integer number T(
Each test case contain a integer N (1
**Output:**
For each case, Print case Number and Desired answer
**Sample:**
Input
Output
2
3
4
Case 1: 2
Case 2: 4