Problem: You are given a positive integer n. Let's build a graph on vertices 1, 2, ..., n in such a way that there is an edge between vertices u and v if and only if <image>. Let d(u, v) be the shortest distance between u and v, or 0 if there is no path between them. Compute the sum of values d(u, v) over all 1 ≤ u < v ≤ n.

The gcd (greatest common divisor) of two positive integers is the maximum positive integer that divides both of the integers.

Input

Single integer n (1 ≤ n ≤ 107).

Output

Print the sum of d(u, v) over all 1 ≤ u < v ≤ n.

Examples

Input

6


Output

8


Input

10


Output

44

Note

All shortest paths in the first example: 

  * <image>
  * <image>
  * <image>
  * <image>
  * <image>
  * <image>



There are no paths between other pairs of vertices.

The total distance is 2 + 1 + 1 + 2 + 1 + 1 = 8.

Solution (in JAVA):

Solution:
import java.util.*;
public class d {
	public static void main(String[] arg) {
		new d();
	}
	public d() {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] smallestPrime = new int[n+1];
		boolean[] isPrime = new boolean[n+1];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		for(int i = 2; i < isPrime.length; i++) {
			if(isPrime[i]) {
				smallestPrime[i] = i;
				for(int j = i+i; j < isPrime.length; j+=i) {
					isPrime[j] = false;
					if(smallestPrime[j] == 0) smallestPrime[j] = i;
				}
			}
		}
		long[] numP = new long[n+1];
		for(int i = 2; i <= n; i++) {
			numP[smallestPrime[i]]++; 
		}
		long[] cum = new long[n+1];
		cum[0] = numP[0];
		for(int i = 1; i <= n; i++) {
			cum[i] += cum[i-1]+numP[i];
		}
		long count2 = 1L * n * (n - 1) / 2 - (n - 1);
		long ans = 0;
		/*
		for(int i = 2; i <= n; i++) {
			int p = smallestPrime[i];
			int other = i/p;
			if(isPrime[other] && other > p) {
//				System.out.println(i + " " + other + " " + numP[p] + " " + numP[other]);
				long temp = numP[p]*numP[other];
				for(int j = p; j <= n; j+=p) {
					if(j % other == 0 && smallestPrime[j] == p)
						temp -= numP[other];
				}
				ans += 2*temp;
			}
		}*/
		outer:
		for(int i = 2; i <= n; i++) {
			long count = 0;
			int sign = -1;
			int x = i;
			while(x > 1) {
				int y = smallestPrime[x];
				x /= y;
				if(smallestPrime[x] == y) {
					continue outer;
				}
				sign *= -1;
			}
			for(int j = i; j <= n; j += i) {
				count++;
			}
			count2 -= sign*(count*(count-1)/2);
			ans += sign*(count*(count-1)/2);
		}
		for(int i = 2; i <= n; i++) {
			if(!isPrime[i]) continue;
			if(n / 2 <= i) continue;
			long c = cum[n / 2];
			c -= cum[Math.max(n / i, i)];
			ans += numP[i]*c*3;
			count2 -= numP[i]*c;
		}
		//System.err.println(count2);
		long numSpec = 0;
		for (int i = 2; i <= n; i++) {
			if (smallestPrime[i] * 2 > n) {
				numSpec++;
			}
		}
		count2 -= (n - 2) * numSpec;
		count2 += numSpec * (numSpec - 1) / 2;
		//System.err.println(count2);
		ans += count2 * 2;
		System.out.println(ans);
	}
}