vaishnav-and-pizzas

As we have seen that Vaishnav was a smart kid and today he has grown up(but he is still childish)
and he is in High school.

Today he was back from school and found that 4 pieces of Pizza was
ordered- one for his father, one for this mother, and one for Vaishnavi and one for him. But
Vaishnav was little late from school and when he came back he found that little Vaishnavi ate half
of his PIZZA. And both of them started fighting. And as usual Vaishnav being the elder one got
punished. 

He was not in a mood to study today. Late at night he came to know that he has a Math
problem to do and he is not in a mood to do. If he does not do the home-work he will be thrown out
of the class the very next day. So he asks you for help. 

He knows that you are the best person to do
the home work as you are good in math.
The question is like that given a number N we have to find the number of positive rational numbers
which is less than 1 so that when it is expressed as P/Q it will be less than one and both P and Q
will be less than or equal to N.

Input:

The first line contains T, the number of test cases.
Followed by T lines each contain N.

Output:

Print the N lines for the output of each query.

Constraints :

   1 ≤ T ≤ 10000
   1 ≤ N ≤ 10000

Problem Setter : Bipin Baburaj

Problem Tester : Darshak Mehta

SAMPLE INPUT
3
4
5
6

SAMPLE OUTPUT
5
9
11

Source: hackerearth | Difficulty: EASY


Solutions:
# http://www.hackerearth.com/tcetcyphers-2/algorithm/vaishnav-and-pizzas/


LIMIT = 10010
phi = [i for i in range(LIMIT)]
for i in range(2, LIMIT):
	if phi[i] == i:
		j = i
		while j < LIMIT:
			phi[j] = phi[j] / i * (i - 1)
			j += i

for i in range(2, LIMIT):
	phi[i] += phi[i - 1]

t = int(input())
for _ in range(t):
	n = int(input())
	print(phi[n] - 1)


# http://www.hackerearth.com/tcetcyphers-2/algorithm/vaishnav-and-pizzas/


LIMIT = 10010
phi = [i for i in range(LIMIT)]
for i in range(2, LIMIT):
	if phi[i] == i:
		j = i
		while j < LIMIT:
			phi[j] = phi[j] / i * (i - 1)
			j += i
phi[1] = 0
for i in range(2, LIMIT):
	phi[i] += phi[i - 1]

t = int(input())
for _ in range(t):
	n = int(input())
	print(phi[n])