{"raw_statement":[{"iden":"statement","content":"Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry.\n\nHe bought _n_ pieces of jewelry. The _i_\\-th piece has price equal to _i_ + 1, that is, the prices of the jewelry are 2, 3, 4, ... _n_ + 1.\n\nWatson gave Sherlock a challenge to color these jewelry pieces such that two pieces don't have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used.\n\nHelp Sherlock complete this trivial task."},{"iden":"input","content":"The only line contains single integer _n_ (1 ≤ _n_ ≤ 100000) — the number of jewelry pieces."},{"iden":"output","content":"The first line of output should contain a single integer _k_, the minimum number of colors that can be used to color the pieces of jewelry with the given constraints.\n\nThe next line should consist of _n_ space-separated integers (between 1 and _k_) that specify the color of each piece in the order of increasing price.\n\nIf there are multiple ways to color the pieces using _k_ colors, you can output any of them."},{"iden":"examples","content":"Input\n\n3\n\nOutput\n\n2\n1 1 2 \n\nInput\n\n4\n\nOutput\n\n2\n2 1 1 2"},{"iden":"note","content":"In the first input, the colors for first, second and third pieces of jewelry having respective prices 2, 3 and 4 are 1, 1 and 2 respectively.\n\nIn this case, as 2 is a prime divisor of 4, colors of jewelry having prices 2 and 4 must be distinct."}],"translated_statement":[{"iden":"statement","content":"Sherlock 有了一个新女朋友（这可真不像他！）。情人节快到了，他想送她一些珠宝。\n\n他买了 #cf_span[n] 件珠宝。第 #cf_span[i] 件珠宝的价格为 #cf_span[i + 1]，即珠宝的价格为 #cf_span[2, 3, 4, ... n + 1]。\n\nWatson 给 Sherlock 一个挑战：将这些珠宝染色，使得如果一件珠宝的价格是另一件珠宝价格的质因数，则这两件珠宝不能有相同的颜色。同时，Watson 要求他最小化使用的不同颜色数量。\n\n请帮助 Sherlock 完成这个简单的任务。\n\n输入仅包含一行，一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）——珠宝的数量。\n\n输出的第一行应包含一个整数 #cf_span[k]，表示在满足上述约束条件下可使用的最少颜色数。\n\n第二行应包含 #cf_span[n] 个用空格分隔的整数（范围在 #cf_span[1] 到 #cf_span[k] 之间），按价格递增顺序指定每件珠宝的颜色。\n\n如果存在多种使用 #cf_span[k] 种颜色的染色方案，输出任意一种即可。\n\n在第一个输入中，价格分别为 #cf_span[2]、#cf_span[3] 和 #cf_span[4] 的第一、第二和第三件珠宝的颜色分别为 #cf_span[1]、#cf_span[1] 和 #cf_span[2]。\n\n在这种情况下，由于 #cf_span[2] 是 #cf_span[4] 的质因数，因此价格为 #cf_span[2] 和 #cf_span[4] 的珠宝颜色必须不同。"},{"iden":"input","content":"输入仅包含一行，一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）——珠宝的数量。"},{"iden":"output","content":"输出的第一行应包含一个整数 #cf_span[k]，表示在满足上述约束条件下可使用的最少颜色数。第二行应包含 #cf_span[n] 个用空格分隔的整数（范围在 #cf_span[1] 到 #cf_span[k] 之间），按价格递增顺序指定每件珠宝的颜色。如果存在多种使用 #cf_span[k] 种颜色的染色方案，输出任意一种即可。"},{"iden":"examples","content":"输入\n3\n输出\n2\n1 1 2\n\n输入\n4\n输出\n2\n2 1 1 2"},{"iden":"note","content":"在第一个输入中，价格分别为 #cf_span[2]、#cf_span[3] 和 #cf_span[4] 的第一、第二和第三件珠宝的颜色分别为 #cf_span[1]、#cf_span[1] 和 #cf_span[2]。在这种情况下，由于 #cf_span[2] 是 #cf_span[4] 的质因数，因此价格为 #cf_span[2] 和 #cf_span[4] 的珠宝颜色必须不同。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 100000 $.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $ where $ p_i = i + 1 $, i.e., $ P = \\{2, 3, 4, \\dots, n+1\\} $.\n\n**Constraints**  \nFor any two distinct elements $ a, b \\in P $, if there exists a prime $ q $ such that $ q \\mid a $ and $ q \\mid b $, then $ a $ and $ b $ must be assigned different colors **if** one is a prime divisor of the other.  \nMore precisely: if $ a, b \\in P $, $ a \\neq b $, and $ \\exists $ prime $ q $ such that $ q \\mid a $ and $ q \\mid b $, **and** either $ a = q $ and $ q \\mid b $, or $ b = q $ and $ q \\mid a $, then $ \\text{color}(a) \\neq \\text{color}(b) $.\n\n**Objective**  \nMinimize the number of colors $ k $ such that a coloring $ c: P \\to \\{1, 2, \\dots, k\\} $ exists satisfying the above constraint.  \nOutput $ k $ and a valid coloring $ c(p_1), c(p_2), \\dots, c(p_n) $.","simple_statement":null,"has_page_source":false}