题目描述

你是一位德高望重的人民教师，这一次，你在为了挑选组团去打 ACM 的队员而发愁。 你现在手底下有 n 名学生，你需要在这些学生中挑选出 n 名队员去打ACM，然而，你发现，这些学生有些是互相认识的，有些是互相不认识的，十分巧合的是，第 i 名队员和第 j 名队员认识，当且仅当 gcd（i，j) > 1。这就使你十分犯愁了，如果你挑选的三名队员中既有互相认识 的，又有互相不认识的，那么这三个人就会更倾向于和认识的那个 人说话，不利于团队建设，所以，你想知道你有多少种方案使得挑 选出的三个人要么互相都认识，要么互相都不认识。

输入格式

一行一个整数 $n (3\\leq n \\leq 2×10^6)$ 表示你的学生数目。

输出格式

一行一个整数表示组队的方案数。

样例

3

1

100000

76825824336806