{"raw_statement":[{"iden":"statement","content":"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 . 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_.\n\nThe _gcd_ (greatest common divisor) of two positive integers is the maximum positive integer that divides both of the integers."},{"iden":"input","content":"Single integer _n_ (1 ≤ _n_ ≤ 107)."},{"iden":"output","content":"Print the sum of _d_(_u_, _v_) over all 1 ≤ _u_ < _v_ ≤ _n_."},{"iden":"examples","content":"Input\n\n6\n\nOutput\n\n8\n\nInput\n\n10\n\nOutput\n\n44"},{"iden":"note","content":"All shortest paths in the first example:\n\nThere are no paths between other pairs of vertices.\n\nThe total distance is 2 + 1 + 1 + 2 + 1 + 1 = 8."}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"给定一个正整数 $n$。在顶点 $1, 2, ..., n$ 上构建一个图，使得当且仅当 $\\gcd(u, v) > 1$ 时，顶点 $u$ 和 $v$ 之间有一条边。令 $d(u, v)$ 表示 $u$ 和 $v$ 之间的最短距离，若它们之间无路径则为 $0$。计算所有 $1 ≤ u < v ≤ n$ 的 $d(u, v)$ 之和。\\n\\n两个正整数的最大公约数（$\\gcd$）是能同时整除这两个整数的最大正整数。\\n\\n单个整数 $n$（$1 ≤ n ≤ 10^7$）。\\n\\n请输出所有 $1 ≤ u < v ≤ n$ 的 $d(u, v)$ 之和。\\n\\n第一个示例中的所有最短路径：\\n\\n其他顶点对之间不存在路径。\\n\\n总距离为 $2 + 1 + 1 + 2 + 1 + 1 = 8$。\\n\\n\"},{\"iden\":\"input\",\"content\":\"单个整数 $n$（$1 ≤ n ≤ 10^7$）。\"},{\"iden\":\"output\",\"content\":\"请输出所有 $1 ≤ u < v ≤ n$ 的 $d(u, v)$ 之和。\"},{\"iden\":\"examples\",\"content\":\"输入6输出8输入10输出44\"},{\"iden\":\"note\",\"content\":\"第一个示例中的所有最短路径：              其他顶点对之间不存在路径。总距离为 $2 + 1 + 1 + 2 + 1 + 1 = 8$。\"}]","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10^7 $.  \nDefine a graph $ G = (V, E) $ where $ V = \\{1, 2, \\dots, n\\} $, and $ (u, v) \\in E $ if and only if $ \\gcd(u, v) > 1 $.  \n\nLet $ d(u, v) $ denote the shortest path distance between vertices $ u $ and $ v $ in $ G $, with $ d(u, v) = 0 $ if $ u $ and $ v $ are in different connected components.\n\n**Constraints**  \n$ 1 \\leq n \\leq 10^7 $\n\n**Objective**  \nCompute:  \n$$\n\\sum_{1 \\leq u < v \\leq n} d(u, v)\n$$","simple_statement":null,"has_page_source":false}