神秘密码组合

题目背景

在数字王国中，有一个古老的密码锁。

密码锁由三个不同的数字组成：

(a, b, c)

其中：

• 三个数字必须来自 1 ~ n；
• 三个数字不能重复；
• 三个数字之间必须满足特殊规则：

任意两个数字的最大公约数都必须为 1。

也就是说：

gcd(a,b)=1
gcd(a,c)=1
gcd(b,c)=1

这样的三个数字称为一个合法密码组合。

现在，请你帮助守护者计算：

从 1 到 n 中，一共有多少种不同的合法密码组合？

输入格式

输入一个整数：

n

表示数字范围为：

1,2,3,...,n

输出格式

输出一个整数：

表示合法密码组合的数量。

数据范围

3 ≤ n ≤ 200

保证答案可以使用 int 存储。

样例输入1

5

样例输出1

4

样例解释

数字范围：

1 2 3 4 5

所有合法组合：

(1,2,3)

(1,2,4)

(1,2,5)

(1,3,4)

(1,3,5)

(1,4,5)

(2,3,4)

(2,3,5)

(2,4,5)

(3,4,5)

逐个判断：

(1,2,3)
gcd(1,2)=1
gcd(1,3)=1
gcd(2,3)=1
合法

(2,4,5)
gcd(2,4)=2

不合法。

最终合法组合：

(1,2,3)
(1,2,4)
(1,2,5)
(1,3,4)

答案：

4