1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <cstdint>
#include <cstdio>
#include <vector>

void solve(const int& n) {
  const std::vector<uint16_t> solutions({
      0,   0,    0,    2,    0,   0,    2,    3,    0,   7,    0,    5,    2,    3,    3,    8,    0,   5,    7,    8,    0,    17,   5,    9,    2,   6,    3,    21,   3,    9,    8,    12,
      0,   26,   5,    15,   7,   12,   8,    23,   0,   14,   17,   17,   5,    31,   9,    18,   2,   24,   6,    32,   3,    18,   21,   23,   3,   41,   9,    23,   8,    21,   12,   58,
      0,   18,   26,   26,   5,   47,   15,   27,   7,   26,   12,   44,   8,    44,   23,   30,   0,   62,   14,   32,   17,   26,   17,   53,   5,   32,   31,   42,   9,    62,   18,   38,
      2,   35,   24,   86,   6,   36,   32,   39,   3,   83,   18,   41,   21,   39,   23,   68,   3,   41,   41,   45,   9,    82,   23,   56,   8,   55,   21,   77,   12,   42,   58,   48,
      0,   86,   18,   50,   26,  71,   26,   99,   5,   50,   47,   53,   15,   92,   27,   62,   7,   48,   26,   122,  12,   54,   44,   57,   8,   110,  44,   60,   23,   57,   30,   98,
      0,   84,   62,   62,   14,  122,  32,   63,   17,  60,   26,   137,  17,   63,   53,   81,   5,   116,  32,   68,   31,   66,   42,   113,  9,   63,   62,   83,   18,   180,  38,   72,
      2,   71,   35,   116,  24,  72,   86,   75,   6,   131,  36,   96,   32,   71,   39,   160,  3,   104,  83,   80,   18,   137,  41,   83,   21,  111,  39,   137,  23,   77,   68,   84,
      3,   157,  41,   86,   41,  84,   45,   221,  9,   86,   82,   90,   23,   152,  56,   90,   8,   89,   55,   184,  21,   120,  77,   101,  12,  161,  42,   95,   58,   122,  48,   155,
      0,   95,   86,   123,  18,  184,  50,   99,   26,  93,   71,   167,  26,   99,   99,   102,  5,   218,  50,   119,  47,   102,  53,   211,  15,  104,  92,   107,  27,   197,  62,   137,
      7,   106,  48,   182,  26,  108,  122,  113,  12,  263,  54,   120,  44,   152,  57,   188,  8,   108,  110,  116,  44,   197,  60,   117,  23,  116,  57,   286,  30,   117,  98,   140,
      0,   206,  84,   134,  62,  111,  62,   203,  14,  165,  122,  125,  32,   235,  63,   128,  17,  125,  60,   212,  26,   161,  137,  171,  17,  233,  63,   131,  53,   129,  81,   258,
      5,   131,  116,  135,  32,  287,  68,   135,  31,  151,  66,   275,  42,   131,  113,  138,  9,   263,  63,   177,  62,   138,  83,   230,  18,  135,  180,  143,  38,   242,  72,   144,
      2,   218,  71,   290,  35,  144,  116,  158,  24,  251,  72,   150,  86,   147,  75,   356,  6,   149,  131,  159,  36,   302,  96,   179,  32,  152,  71,   257,  39,   206,  160,  158,
      3,   266,  104,  158,  83,  156,  80,   313,  18,  149,  137,  204,  41,   317,  83,   162,  21,  161,  111,  266,  39,   197,  137,  165,  23,  415,  77,   167,  68,   161,  84,   278,
      3,   167,  157,  200,  41,  287,  86,   213,  41,  170,  84,   341,  45,   171,  221,  174,  9,   308,  86,   176,  82,   233,  90,   293,  23,  221,  152,  194,  56,   337,  90,   180,
      8,   174,  89,   422,  55,  176,  184,  183,  21,  311,  120,  185,  77,   179,  101,  416,  12,  246,  161,  188,  42,   317,  95,   189,  58,  183,  122,  314,  48,   189,  155,  245,
      0,   422,  95,   195,  86,  239,  123,  323,  18,  194,  184,  197,  50,   419,  99,   209,  26,  216,  93,   392,  71,   194,  167,  203,  26,  341,  99,   317,  99,   201,  102,  338,
      5,   198,  218,  206,  50,  388,  119,  227,  47,  273,  102,  341,  53,   207,  211,  218,  15,  419,  104,  212,  92,   206,  107,  545,  27,  212,  197,  215,  62,   362,  137,  231,
      7,   215,  106,  362,  48,  287,  182,  257,  26,  409,  108,  221,  122,  260,  113,  368,  12,  221,  263,  281,  54,   377,  120,  225,  44,  224,  152,  443,  57,   271,  188,  228,
      8,   488,  108,  237,  110, 228,  116,  380,  44,  230,  197,  233,  60,   498,  117,  299,  23,  228,  116,  518,  57,   230,  286,  237,  30,  401,  117,  240,  98,   315,  140,  466,
      0,   239,  206,  242,  84,  422,  134,  243,  62,  299,  111,  557,  62,   243,  203,  248,  14,  467,  165,  248,  122,  246,  125,  410,  32,  353,  235,  270,  63,   422,  128,  296,
      17,  251,  125,  495,  60,  252,  212,  326,  26,  431,  161,  257,  137,  251,  171,  428,  17,  252,  233,  260,  63,   749,  131,  263,  53,  257,  129,  437,  81,   261,  258,  290,
      5,   458,  131,  339,  116, 264,  135,  517,  32,  309,  287,  311,  68,   452,  135,  270,  31,  354,  151,  452,  66,   261,  275,  273,  42,  549,  131,  287,  113,  273,  138,  608,
      9,   338,  263,  278,  63,  512,  177,  279,  62,  273,  138,  545,  83,   368,  230,  282,  18,  476,  135,  285,  180,  282,  143,  611,  38,  284,  242,  366,  72,   539,  144,  296,
      2,   287,  218,  482,  71,  288,  290,  306,  35,  623,  144,  323,  116,  356,  158,  576,  24,  288,  251,  296,  72,   497,  150,  380,  86,  291,  147,  491,  75,   297,  356,  311,
      6,   569,  149,  356,  131, 420,  159,  503,  36,  302,  302,  305,  96,   512,  179,  308,  32,  356,  152,  745,  71,   306,  257,  309,  39,  608,  206,  311,  160,  309,  158,  518,
      3,   413,  266,  315,  104, 657,  158,  315,  83,  312,  156,  527,  80,   306,  313,  490,  18,  536,  149,  345,  137,  318,  204,  671,  41,  320,  317,  323,  83,   692,  162,  324,
      21,  318,  161,  542,  111, 395,  266,  335,  39,  620,  197,  417,  137,  327,  165,  548,  23,  329,  415,  332,  77,   572,  167,  333,  68,  435,  161,  791,  84,   386,  278,  338,
      3,   608,  167,  357,  157, 332,  200,  761,  41,  333,  287,  341,  86,   643,  213,  342,  41,  416,  170,  566,  84,   449,  341,  345,  45,  581,  171,  354,  221,  336,  174,  670,
      9,   347,  308,  512,  86,  587,  176,  410,  82,  350,  233,  587,  90,   351,  293,  383,  23,  894,  221,  356,  152,  350,  194,  593,  56,  356,  337,  360,  90,   707,  180,  461,
      8,   384,  174,  698,  89,  356,  422,  363,  55,  674,  176,  365,  184,  476,  183,  599,  21,  365,  311,  434,  120,  694,  185,  369,  77,  363,  179,  827,  101,  422,  416,  372,
      12,  626,  246,  375,  161, 372,  188,  735,  42,  569,  317,  389,  95,   647,  189,  416,  58,  377,  183,  632,  122,  378,  314,  483,  48,  722,  189,  383,  155,  381,  245,  806,
      0,   374,  422,  393,  95,  857,  195,  387,  86,  386,  239,  796,  123,  383,  323,  390,  18,  656,  194,  501,  184,  512,  197,  653,  50,  392,  419,  395,  99,   785,  209,  398,
      26,  516,  216,  662,  93,  396,  392,  399,  71,  683,  194,  473,  167,  399,  203,  977,  26,  396,  341,  419,  99,   677,  317,  413,  99,  459,  201,  755,  102,  555,  338,  408,
      5,   930,  198,  410,  218, 408,  206,  680,  50,  410,  388,  528,  119,  692,  227,  414,  47,  395,  273,  818,  102,  414,  341,  491,  53,  893,  207,  420,  211,  417,  218,  698,
      15,  482,  419,  422,  104, 793,  212,  609,  92,  422,  206,  701,  107,  512,  545,  428,  27,  716,  212,  440,  197,  557,  215,  823,  62,  423,  362,  456,  137,  722,  231,  432,
      7,   431,  215,  1097, 106, 428,  362,  479,  48,  899,  287,  437,  182,  431,  257,  728,  26,  570,  409,  440,  108,  797,  221,  456,  122, 533,  260,  851,  113,  441,  368,  567,
      12,  758,  221,  446,  263, 440,  281,  743,  54,  446,  377,  450,  120,  1208, 225,  530,  44,  449,  224,  752,  152,  446,  443,  464,  57,  803,  271,  582,  188,  453,  228,  910,
      8,   455,  488,  495,  108, 902,  237,  459,  110, 606,  228,  767,  116,  459,  380,  462,  44,  875,  230,  506,  197,  462,  233,  1031, 60,  461,  498,  551,  117,  797,  299,  488,
      23,  467,  228,  902,  116, 611,  518,  473,  57,  791,  230,  473,  286,  467,  237,  788,  30,  608,  401,  609,  117,  975,  240,  506,  98,  545,  315,  788,  140,  477,  466,  480,
      0,   1028, 239,  482,  206, 476,  242,  1079, 84,  482,  422,  485,  134,  812,  243,  618,  62,  485,  299,  812,  111,  486,  557,  489,  62,  919,  243,  491,  203,  746,  248,  986,
      14,  486,  467,  495,  165, 827,  248,  495,  122, 494,  246,  1293, 125,  486,  410,  498,  32,  836,  353,  600,  235,  557,  270,  830,  63,  651,  422,  510,  128,  949,  296,  515,
      17,  498,  251,  842,  125, 575,  495,  650,  60,  1004, 252,  510,  212,  572,  326,  976,  26,  509,  431,  531,  161,  1091, 257,  513,  137, 510,  251,  857,  171,  513,  428,  605,
      17,  1031, 252,  663,  233, 516,  260,  863,  63,  513,  749,  575,  131,  872,  263,  530,  53,  678,  257,  1051, 129,  629,  437,  525,  81,  881,  261,  570,  258,  521,  290,  1166,
      5,   527,  458,  542,  131, 1000, 339,  533,  116, 525,  264,  1103, 135,  705,  517,  534,  32,  983,  309,  536,  287,  534,  311,  1053, 68,  536,  452,  686,  135,  902,  270,  540,
      31,  650,  354,  896,  151, 532,  452,  543,  66,  1435, 261,  545,  275,  543,  273,  905,  42,  606,  549,  548,  131,  917,  287,  923,  113, 543,  273,  1055, 138,  545,  608,  552,
      9,   926,  338,  569,  263, 719,  278,  920,  63,  554,  512,  557,  177,  1295, 279,  558,  62,  557,  273,  1232, 138,  558,  545,  603,  83,  941,  368,  563,  230,  638,  282,  1078,
      18,  758,  476,  668,  135, 947,  285,  567,  180, 563,  282,  941,  143,  563,  611,  804,  38,  1075, 284,  572,  242,  561,  366,  953,  72,  689,  539,  575,  144,  1232, 296,  578,
      2,   570,  287,  1274, 218, 647,  482,  579,  71,  983,  288,  740,  290,  579,  306,  1196, 35,  581,  623,  585,  144,  1102, 323,  585,  116, 759,  356,  977,  158,  581,  576,  588,
      24,  986,  288,  590,  251, 706,  296,  1432, 72,  671,  497,  593,  150,  1052, 380,  594,  86,  588,  291,  1082, 147,  773,  491,  623,  75,  1217, 297,  701,  356,  597,  311,  995,
      6,   599,  569,  771,  149, 1022, 356,  603,  131, 602,  420,  1157, 159,  603,  503,  665,  36,  1586, 302,  608,  302,  606,  305,  1013, 96,  594,  512,  611,  179,  1153, 308,  785,
      32,  684,  356,  1016, 152, 612,  745,  725,  71,  1031, 306,  654,  257,  825,  309,  1212, 39,  614,  608,  627,  206,  1142, 311,  623,  160, 620,  309,  1367, 158,  746,  518,  624,
      3,   1174, 413,  626,  266, 624,  315,  1043, 104, 813,  657,  644,  158,  1097, 315,  683,  83,  628,  312,  1418, 156,  626,  527,  812,  80,  1061, 306,  701,  313,  633,  490,  1055,
      18,  635,  536,  638,  149, 1639, 345,  647,  137, 803,  318,  1067, 204,  639,  671,  662,  41,  1076, 320,  855,  317,  638,  323,  1231, 83,  644,  692,  647,  162,  1169, 324,  764,
      21,  920,  318,  1082, 161, 648,  542,  653,  111, 1232, 395,  678,  266,  651,  335,  1436, 39,  648,  620,  656,  197,  1292, 417,  668,  137, 656,  327,  1287, 165,  854,  548,  660,
      23,  1106, 329,  692,  415, 656,  332,  1301, 77,  657,  572,  1097, 167,  1255, 333,  681,  68,  665,  435,  1112, 161,  662,  791,  669,  84,  1430, 386,  671,  278,  669,  338,  1282,
      3,   806,  608,  675,  167, 1127, 357,  866,  157, 674,  332,  1127, 200,  751,  761,  686,  41,  1376, 333,  680,  287,  900,  341,  1361, 86,  759,  643,  695,  213,  1142, 342,  684,
      41,  674,  416,  1663, 170, 755,  566,  687,  84,  1193, 449,  690,  341,  824,  345,  1148, 45,  894,  581,  764,  171,  1304, 354,  693,  221, 727,  336,  1157, 174,  689,  670,  888,
      9,   1166, 347,  821,  308, 696,  512,  1511, 86,  693,  587,  701,  176,  1502, 410,  702,  82,  701,  350,  1166, 233,  702,  587,  705,  90,  1751, 351,  906,  293,  687,  383,  1175,
      23,  707,  894,  753,  221, 1187, 356,  713,  152, 921,  350,  1361, 194,  711,  593,  842,  56,  1208, 356,  716,  337,  797,  360,  1583, 90,  716,  707,  720,  180,  1452, 461,  794,
      8,   716,  384,  1202, 174, 1094, 698,  752,  89,  1211, 356,  725,  422,  723,  363,  1436, 55,  720,  674,  933,  176,  1217, 365,  749,  184, 723,  476,  1493, 183,  729,  599,  732,
      21,  1894, 365,  791,  311, 827,  434,  1223, 120, 729,  694,  744,  185,  1247, 369,  947,  77,  884,  363,  1454, 179,  738,  827,  756,  101, 1241, 422,  743,  416,  962,  372,  1238,
      12,  738,  626,  746,  246, 1406, 375,  881,  161, 746,  372,  1772, 188,  747,  735,  750,  42,  1358, 569,  752,  317,  746,  389,  1435, 95,  998,  647,  755,  189,  1487, 416,  798,
      58,  755,  377,  1262, 183, 827,  632,  973,  122, 1508, 378,  761,  314,  759,  483,  1268, 48,  860,  722,  896,  189,  1637, 383,  765,  155, 759,  381,  1463, 245,  761,  806,  833,
      0,   1286, 374,  987,  422, 768,  393,  1280, 95,  926,  857,  792,  195,  1459, 387,  774,  86,  1028, 386,  1286, 239,  774,  796,  857,  123, 1301, 383,  794,  323,  854,  390,  2330,
      18,  779,  656,  782,  194, 1322, 501,  783,  184, 782,  512,  1307, 197,  1095, 653,  788,  50,  1487, 392,  788,  419,  941,  395,  1313, 99,  783,  785,  1097, 209,  1457, 398,  792,
      26,  791,  516,  1561, 216, 788,  662,  803,  93,  1703, 396,  941,  392,  782,  399,  1328, 71,  797,  683,  800,  194,  1611, 473,  1023, 167, 800,  399,  1547, 203,  801,  977,  804,
      26,  1580, 396,  890,  341, 1043, 419,  1537, 99,  806,  677,  810,  317,  1352, 413,  821,  99,  809,  459,  1772, 201,  806,  755,  959,  102, 1538, 555,  822,  338,  809,  408,  1349,
      5,   1056, 930,  818,  198, 1367, 410,  845,  218, 983,  408,  1643, 206,  980,  680,  1055, 50,  1439, 410,  825,  388,  819,  528,  1373, 119, 903,  692,  827,  227,  2071, 414,  828,
      47,  864,  395,  1688, 273, 828,  818,  833,  102, 1391, 414,  1068, 341,  831,  491,  1742, 53,  824,  893,  848,  207,  1397, 420,  908,  211, 1271, 417,  1391, 218,  837,  698,  840,
      15,  1694, 482,  842,  419, 836,  422,  1841, 104, 837,  793,  845,  212,  1412, 609,  995,  92,  840,  422,  1616, 206,  1205, 701,  902,  107, 1433, 512,  851,  545,  849,  428,  1418,
      27,  851,  716,  1086, 212, 2075, 440,  893,  197, 854,  557,  1427, 215,  851,  823,  858,  62,  1838, 423,  879,  362,  858,  456,  1688, 137, 860,  722,  1145, 231,  1487, 432,  1194,
      7,   858,  431,  1442, 215, 864,  1097, 867,  106, 1640, 428,  870,  362,  1124, 479,  1448, 48,  1040, 899,  945,  287,  1544, 437,  881,  182, 869,  431,  2122, 257,  873,  728,  878,
      26,  1619, 570,  878,  409, 876,  440,  1781, 108, 1163, 797,  881,  221,  1751, 456,  882,  122, 876,  533,  1466, 260,  882,  851,  1136, 113, 1481, 441,  899,  368,  1097, 567,  1690,
      12,  984,  758,  890,  221, 1907, 446,  980,  263, 890,  440,  1481, 281,  891,  743,  894,  54,  1684, 446,  1448, 377,  894,  450,  1493, 120, 896,  1208, 900,  225,  1562, 530,  900,
      44,  1200, 449,  1772, 224, 882,  752,  923,  152, 1784, 446,  905,  443,  1016, 464,  2108, 57,  905,  803,  938,  271,  1714, 582,  909,  188, 899,  453,  1517, 228,  1178, 910,  1073,
      8,   1526, 455,  915,  488, 912,  495,  1741, 108, 914,  902,  1176, 237,  1547, 459,  918,  110, 1002, 606,  1778, 228,  1097, 767,  923,  116, 2325, 459,  923,  380,  1022, 462,  1538,
      44,  905,  875,  926,  230, 1547, 506,  1190, 197, 926,  462,  2072, 233,  927,  1031, 956,  60,  1556, 461,  939,  498,  1230, 551,  1553, 117, 1049, 797,  972,  299,  1765, 488,  938,
      23,  1118, 467,  2072, 228, 932,  902,  939,  116, 1583, 611,  1020, 518,  935,  473,  1994, 57,  1218, 791,  945,  230,  1577, 473,  1115, 286, 944,  467,  1574, 237,  936,  788,  1354,
      30,  1793, 608,  950,  401, 944,  609,  1574, 117, 1031, 975,  953,  240,  2450, 506,  954,  98,  948,  545,  1820, 315,  954,  788,  957,  140, 1733, 477,  1226, 466,  957,  480,  1598,
      0,   954,  1028, 1136, 239, 2090, 482,  974,  206, 1245, 476,  1607, 242,  1052, 1079, 981,  84,  1616, 482,  968,  422,  962,  485,  2354, 134, 1193, 812,  978,  243,  1622, 618,  972,
      62,  971,  485,  1616, 299, 1290, 812,  1058, 111, 1845, 486,  1079, 557,  971,  489,  1976, 62,  977,  919,  1257, 243,  1682, 491,  983,  203, 980,  746,  1931, 248,  981,  986,  1028,
      14,  2105, 486,  1011, 467, 1175, 495,  1643, 165, 986,  827,  1046, 248,  1867, 495,  1266, 122, 1112, 494,  1652, 246,  1080, 1293, 993,  125, 1661, 486,  1175, 410,  1286, 498,  1946,
      32,  995,  836,  998,  353, 1667, 600,  999,  235, 980,  557,  2177, 270,  995,  830,  1002, 63,  2372, 651,  1019, 422,  1002, 510,  1931, 128, 1299, 949,  1007, 296,  1697, 515,  1008,
      17,  1007, 498,  2071, 251, 1008, 842,  1583, 125, 1793, 575,  1013, 495,  1007, 650,  1685, 60,  1008, 1004, 1016, 252,  2585, 510,  1017, 212, 1016, 572,  1691, 326,  1331, 976,  1020,
      26,  1706, 509,  1311, 431, 1011, 531,  2007, 161, 1022, 1091, 1025, 257,  1712, 513,  1028, 137, 1433, 510,  2078, 251,  1026, 857,  1037, 171, 1939, 513,  1061, 428,  1029, 605,  2246,
      17,  1031, 1031, 1136, 252, 1727, 663,  1100, 233, 1235, 516,  1973, 260,  1365, 863,  1038, 63,  1778, 513,  1052, 749,  1121, 575,  1724, 131, 1040, 872,  1338, 263,  2088, 530,  1360,
      53,  1038, 678,  1742, 257, 1044, 1051, 1047, 129, 2561, 629,  1091, 437,  1047, 525,  1996, 81,  1049, 881,  1052, 261,  2072, 570,  1352, 258, 1050, 521,  1757, 290,  1049, 1166, 1058,
      5,   1997, 527,  1058, 458, 1446, 542,  1763, 131, 1049, 1000, 1253, 339,  1922, 533,  1172, 116, 1061, 525,  2717, 264,  1062, 1103, 1076, 135, 1781, 705,  1067, 517,  1061, 534,  1775,
      32,  1622, 983,  1070, 309, 2020, 536,  1073, 287, 1070, 534,  1787, 311,  1071, 1053, 1379, 68,  1808, 536,  1119, 452,  1205, 686,  2405, 135, 1067, 902,  1167, 270,  2312, 540,  1080,
      31,  1166, 650,  1922, 354, 1076, 896,  1083, 151, 2171, 532,  1487, 452,  1292, 543,  1805, 66,  1085, 1435, 1095, 261,  1817, 545,  1089, 275, 1433, 543,  2285, 273,  1089, 905,  1121,
      42,  1826, 606,  1286, 549, 1092, 548,  2381, 131, 1209, 917,  1122, 287,  2062, 923,  1098, 113, 1092, 543,  1832, 273,  1421, 1055, 1103, 138, 2174, 545,  1103, 608,  1097, 552,  2166,
      9,   1298, 926,  1419, 338, 1847, 569,  1115, 263, 1106, 719,  1841, 278,  1107, 920,  1310, 63,  2812, 554,  1112, 512,  1106, 557,  2111, 177, 1112, 1295, 1115, 279,  1862, 558,  1424,
      62,  1110, 557,  2126, 273, 1331, 1232, 1235, 138, 1883, 558,  1140, 545,  1485, 603,  1868, 83,  1118, 941,  1125, 368,  2234, 563,  1125, 230, 1124, 638,  2852, 282,  1121, 1078, 1199,
      18,  1949, 758,  1130, 476, 1247, 668,  2201, 135, 1461, 947,  1133, 285,  2087, 567,  1134, 180, 1357, 563,  1892, 282,  1130, 941,  1460, 143, 2150, 563,  1140, 611,  1137, 804,  1898,
      38,  1139, 1075, 1154, 284, 2441, 572,  1349, 242, 1142, 561,  2249, 366,  1232, 953,  1188, 72,  1916, 689,  1772, 539,  1146, 575,  1913, 144, 1143, 1232, 1151, 296,  2738, 578,  1178,
      2,   1488, 570,  1913, 287, 1148, 1274, 1155, 218, 1973, 647,  1157, 482,  1151, 579,  2914, 71,  1157, 983,  1370, 288,  1937, 740,  1163, 290, 1301, 579,  1937, 306,  1502, 1196, 1184,
      35,  2484, 581,  1173, 623, 1164, 585,  1940, 144, 1391, 1102, 1496, 323,  1952, 585,  1170, 116, 1169, 759,  2228, 356,  1164, 977,  1211, 158, 2513, 581,  1248, 576,  1169, 588,  2564,
      24,  1175, 986,  1232, 288, 2224, 590,  1514, 251, 1160, 706,  1967, 296,  1268, 1432, 1283, 72,  1976, 671,  1185, 497,  1799, 593,  2365, 150, 1179, 1052, 1187, 380,  1997, 594,  1188,
      86,  1187, 588,  2582, 291, 1331, 1082, 1206, 147, 2252, 773,  1409, 491,  1191, 623,  1988, 75,  1578, 1217, 1196, 297,  1997, 701,  1197, 356, 1299, 597,  2326, 311,  1322, 995,  1541,
      6,   2369, 599,  1202, 569, 1196, 771,  2003, 149, 1202, 1022, 1328, 356,  3044, 603,  1208, 131, 1205, 602,  2006, 420,  1206, 1157, 1427, 159, 2108, 603,  1554, 503,  1209, 665,  2302,
      36,  1206, 1586, 1215, 302, 2072, 608,  1244, 302, 1569, 606,  2297, 305,  1487, 1013, 1229, 96,  2562, 594,  1220, 512,  1218, 611,  2783, 179, 1220, 1153, 1223, 308,  2042, 785,  1232,
      32,  1218, 684,  2890, 356, 1583, 1016, 1227, 152, 2051, 612,  1244, 745,  1223, 725,  2048, 71,  1226, 1031, 1682, 306,  2324, 654,  1361, 257, 1583, 825,  2057, 309,  1229, 1212, 1238,
      39,  2648, 614,  1238, 608, 1236, 627,  2353, 206, 1233, 1142, 1241, 311,  2072, 623,  1976, 160, 1241, 620,  2054, 309,  1349, 1367, 1245, 158, 2480, 746,  1247, 518,  1769, 624,  2078,
      3,   1247, 1174, 1250, 413, 2462, 626,  1353, 266, 1341, 624,  3040, 315,  1247, 1043, 1254, 104, 2108, 813,  1256, 657,  1250, 644,  2093, 158, 1623, 1097, 1481, 315,  2377, 683,  1260,
      83,  1259, 628,  2408, 312, 1256, 1418, 1617, 156, 2111, 626,  1265, 527,  1263, 812,  2481, 80,  1508, 1061, 1347, 306,  3047, 701,  1280, 313, 1263, 633,  2117, 490,  1269, 1055, 1272,
      18,  2398, 635,  1631, 536, 1367, 638,  2561, 149, 1427, 1639, 1307, 345,  2147, 647,  1278, 137, 1650, 803,  2432, 318,  1278, 1067, 1283, 204, 2204, 639,  1290, 671,  1526, 662,  2786,
      41,  1274, 1076, 1395, 320, 2565, 855,  1340, 317, 1286, 638,  2141, 323,  1664, 1231, 1424, 83,  2288, 644,  1526, 692,  1272, 647,  2455, 162, 1292, 1169, 1658, 324,  2162, 764,  1298,
      21,  1295, 920,  2162, 318, 1296, 1082, 1299, 161, 3731, 648,  1301, 542,  1299, 653,  2165, 111, 1434, 1232, 1319, 395,  2402, 678,  1779, 266, 1351, 651,  2723, 335,  1289, 1436, 1544,
      39,  2186, 648,  1310, 620, 1691, 656,  2180, 197, 1305, 1292, 1313, 417,  2479, 668,  1397, 137, 1308, 656,  2852, 327,  1576, 1287, 1317, 165, 2201, 854,  1451, 548,  1317, 660,  2711,
      23,  1704, 1106, 1329, 329, 2294, 692,  1323, 415, 1322, 656,  2663, 332,  1323, 1301, 1698, 77,  2648, 657,  1328, 572,  1326, 1097, 2213, 167, 1323, 1255, 1331, 333,  2849, 681,  1370,
      68,  1745, 665,  2581, 435, 1332, 1112, 1335, 161, 2231, 662,  1716, 791,  1545, 669,  2225, 84,  1436, 1430, 1340, 386,  2530, 671,  1574, 278, 1778, 669,  2237, 338,  1341, 1282, 1344,
      3,   2258, 806,  1358, 608, 1340, 675,  3761, 167, 1346, 1127, 1350, 357,  2657, 866,  1394, 157, 1344, 674,  2252, 332,  1770, 1127, 1353, 200, 2558, 751,  1470, 761,  1353, 686,  2255,
      41,  1355, 1376, 2150, 333, 2327, 680,  1359, 287, 1344, 900,  2734, 341,  1520, 1361, 1362, 86,  2918, 759,  1365, 643,  1362, 695,  2273, 213, 1625, 1142, 1367, 342,  2733, 684,  1757,
      41,  1364, 674,  2282, 416, 1364, 1663, 1430, 170, 2483, 755,  1373, 566,  1772, 687,  3068, 84,  1368, 1193, 1520, 449,  2297, 690,  1377, 341, 1376, 824,  3044, 345,  1377, 1148, 1388,
      45,  2609, 894,  1401, 581, 1682, 764,  2303, 171, 1892, 1304, 1385, 354,  2312, 693,  1388, 221, 1385, 727,  2726, 336,  1386, 1157, 1947, 174, 2555, 689,  1643, 670,  1389, 888,  2318,
      9,   1488, 1166, 1395, 347, 3503, 821,  1395, 308, 1392, 696,  2327, 512,  1386, 1511, 1398, 86,  2759, 693,  1793, 587,  1398, 701,  2711, 176, 1395, 1502, 1403, 410,  2447, 702,  1550,
      82,  1838, 701,  2342, 350, 1547, 1166, 1795, 233, 2807, 702,  1410, 587,  1399, 705,  3056, 90,  1409, 1751, 1449, 351,  2372, 906,  1413, 293, 1412, 687,  2687, 383,  2228, 1175, 1431,
      23,  2366, 707,  1418, 894, 1583, 753,  2360, 221, 1413, 1187, 1824, 356,  2683, 713,  1433, 152, 1421, 921,  3047, 350,  1422, 1361, 1445, 194, 3053, 711,  1427, 593,  1421, 842,  2960,
      56,  1422, 1208, 1455, 356, 2537, 716,  1833, 337, 1703, 797,  2723, 360,  1431, 1583, 1434, 90,  2702, 716,  1502, 707,  1853, 720,  2393, 180, 1436, 1452, 1481, 461,  2402, 794,  1700,
      8,   1584, 716,  3499, 384, 1436, 1202, 1443, 174, 2411, 1094, 1445, 698,  1443, 752,  2405, 89,  2054, 1211, 1460, 356,  3362, 725,  1449, 422, 1443, 723,  2417, 363,  1445, 1436, 1974,
      55,  2426, 720,  1542, 674, 1452, 933,  2761, 176, 1454, 1217, 1721, 365,  3116, 749,  1581, 184, 1457, 723,  2432, 476,  1454, 1493, 1610, 183, 2762, 729,  1878, 599,  1562, 732,  2438,
      21,  1778, 1894, 1466, 365, 2447, 791,  1467, 311, 1973, 827,  2877, 434,  1467, 1223, 1470, 120, 2456, 729,  1472, 694,  1461, 744,  3734, 185, 1472, 1247, 1475, 369,  3350, 947,  1478,
      77,  1596, 884,  2456, 363, 1907, 1454, 1479, 179, 2483, 738,  1481, 827,  1760, 756,  2812, 101, 1580, 1241, 1901, 422,  2477, 743,  1511, 416, 1481, 962,  2477, 372,  1467, 1238, 1488,
      12,  3926, 738,  1958, 626, 1484, 746,  2474, 246, 1487, 1406, 1620, 375,  2492, 881,  1919, 161, 1488, 746,  2840, 372,  1494, 1772, 1505, 188, 2999, 747,  1556, 735,  1934, 750,  2786,
      42,  1499, 1358, 1502, 569, 2834, 752,  1503, 317, 1679, 746,  3257, 389,  1503, 1435, 1775, 95,  2558, 998,  1508, 647,  1506, 755,  2961, 189, 2106, 1487, 1511, 416,  2582, 798,  1532,
      58,  1506, 755,  2516, 377, 1799, 1262, 1946, 183, 2864, 827,  1524, 632,  1511, 973,  2876, 122, 1517, 1508, 1520, 378,  3257, 761,  1523, 314, 1520, 759,  3407, 483,  1646, 1268, 1535,
      48,  2558, 860,  2072, 722, 1520, 896,  2861, 189, 1526, 1637, 1544, 383,  3042, 765,  1530, 155, 2324, 759,  2552, 381,  1772, 1463, 1577, 245, 2663, 761,  1535, 806,  1533, 833,  3724,
      0,   1532, 1286, 1538, 374, 2567, 987,  1817, 422, 1533, 768,  2564, 393,  1988, 1280, 1542, 95,  2915, 926,  1545, 857,  1697, 792,  2573, 195, 1539, 1459, 2339, 387,  3044, 774,  1548,
      86,  1547, 1028, 3098, 386, 1548, 1286, 1553, 239, 3323, 774,  1553, 796,  1547, 857,  2588, 123, 1548, 1301, 1832, 383,  2938, 794,  2000, 323, 1556, 854,  2591, 390,  1557, 2330, 1560,
      18,  2879, 779,  1695, 656, 2066, 782,  2965, 194, 1859, 1322, 1637, 501,  2657, 783,  1581, 184, 1565, 782,  3392, 512,  1562, 1307, 1634, 197, 3279, 1095, 1608, 653,  1670, 788,  3146,
      50,  2028, 1487, 1575, 392, 2627, 788,  1736, 419, 1574, 941,  2993, 395,  1566, 1313, 2027, 99,  2858, 783,  1580, 785,  1877, 1097, 2630, 209, 1580, 1457, 1583, 398,  3962, 792,  1613,
      26,  1566, 791,  2642, 516, 1584, 1561, 1587, 216, 2714, 788,  2446, 662,  1772, 803,  3120, 93,  1589, 1703, 1592, 396,  2672, 941,  1694, 392, 2055, 782,  2651, 399,  1593, 1328, 1728,
      71,  3740, 797,  1598, 683, 1596, 800,  3533, 194, 1593, 1611, 1613, 473,  2672, 1023, 1602, 167, 1601, 800,  3347, 399,  2148, 1547, 1895, 203, 2681, 801,  1607, 977,  1601, 804,  2678,
      26,  1607, 1580, 2067, 396, 3200, 890,  1613, 341, 1610, 1043, 2687, 419,  2072, 1537, 1622, 99,  3455, 806,  1670, 677,  1745, 810,  3067, 317, 1805, 1352, 1620, 413,  2702, 821,  2081,
      99,  1614, 809,  3248, 459, 1611, 1772, 1623, 201, 3061, 806,  1668, 755,  2096, 959,  2702, 102, 1625, 1538, 1628, 555,  2717, 822,  1703, 338, 1973, 809,  4473, 408,  1629, 1349, 1802,
      5,   2726, 1056, 1676, 930, 1632, 818,  2723, 198, 2168, 1367, 1637, 410,  3089, 845,  1934, 218, 1634, 983,  3032, 408,  1638, 1643, 2103, 206, 2741, 980,  1662, 680,  1637, 1055, 3118,
      50,  1638, 1439, 1676, 410, 4613, 825,  1647, 388, 1809, 819,  2741, 528,  1647, 1373, 1688, 119, 3284, 903,  2117, 692,  1646, 827,  2750, 227, 1652, 2071, 1955, 414,  2762, 828,  1658,
      47,  2136, 864,  3146, 395, 1656, 1688, 1659, 273, 2858, 828,  1835, 818,  1772, 833,  3596, 102, 2090, 1391, 1665, 414,  3140, 1068, 1808, 341, 1664, 831,  2777, 491,  2175, 1742, 1668,
      53,  2786, 824,  1670, 893, 1664, 848,  3929, 207, 1670, 1397, 2226, 420,  2792, 908,  1674, 211, 1928, 1271, 2792, 417,  1670, 1391, 1688, 218, 4189, 837,  1694, 698,  2011, 840,  2798,
      15,  1679, 1694, 1682, 482, 3041, 842,  2162, 419, 1735, 836,  3197, 422,  1683, 1841, 1788, 104, 2816, 837,  1994, 793,  2177, 845,  3191, 212, 1670, 1412, 1691, 609,  3360, 995,  1700,
      92,  1691, 840,  3797, 422, 1692, 1616, 1695, 206, 3344, 1205, 1697, 701,  1686, 902,  3220, 107, 2190, 1433, 1845, 512,  2837, 851,  1703, 545, 1695, 849,  2837, 428,  1898, 1418, 2678,
      27,  3214, 851,  1706, 716, 1704, 1086, 2840, 212, 1701, 2075, 1710, 440,  4022, 893,  1781, 197, 1709, 854,  3357, 557,  2072, 1427, 1713, 215, 2861, 851,  2202, 823,  1709, 858,  2849,
      62,  1884, 1838, 1898, 423, 3244, 879,  1719, 362, 2243, 858,  3443, 456,  1715, 1688, 1722, 137, 2876, 860,  1725, 722,  1722, 1145, 4190, 231, 1841, 1487, 1727, 432,  2897, 1194, 1739,
      7,   2054, 858,  2876, 431, 2231, 1442, 1773, 215, 3827, 864,  1842, 1097, 1731, 867,  3236, 106, 1719, 1640, 2229, 428,  2897, 870,  2051, 362, 1733, 1124, 3346, 479,  1737, 1448, 1740,
      48,  3725, 1040, 1742, 899, 1736, 945,  2903, 287, 1742, 1544, 1745, 437,  4064, 881,  2558, 182, 1745, 869,  2912, 431,  1853, 2122, 1749, 257, 2933, 873,  1758, 728,  2445, 878,  3438,
      26,  1751, 1619, 2063, 570, 2927, 878,  1755, 409, 1893, 876,  3797, 440,  1751, 1781, 1838, 108, 3323, 1163, 1760, 797,  1954, 881,  2930, 221, 2675, 1751, 1788, 456,  2942, 882,  1764,
      122, 1758, 876,  3350, 533, 1760, 1466, 2270, 260, 2951, 882,  1916, 851,  1763, 1136, 3536, 113, 1769, 1481, 1772, 441,  4470, 899,  1793, 368, 1772, 1097, 3353, 567,  1773, 1690, 1778,
      12,  2966, 984,  2283, 758, 2111, 890,  3578, 221, 1760, 1907, 1854, 446,  2972, 980,  1782, 263, 2363, 890,  2966, 440,  1889, 1481, 1785, 281, 3679, 891,  2111, 743,  1781, 894,  3866,
      54,  1994, 1684, 1797, 446, 3122, 1448, 1806, 377, 1787, 894,  3689, 450,  2312, 1493, 1794, 120, 3530, 896,  1796, 1208, 1794, 900,  2993, 225, 1796, 1562, 2306, 530,  3395, 900,  1800,
      44,  1799, 1200, 3002, 449, 1920, 1772, 2561, 224, 3863, 882,  1817, 752,  1803, 923,  3476, 152, 1805, 1784, 1851, 446,  3017, 905,  2319, 443, 1799, 1016, 3017, 464,  2150, 2108, 1812,
      57,  3602, 905,  1815, 803, 2339, 938,  3023, 271, 1929, 1714, 1836, 582,  3347, 909,  1844, 188, 1812, 899,  5390, 453,  1997, 1517, 1823, 228, 3041, 1178, 1907, 910,  1821, 1073, 3038,
      8,   2378, 1526, 1941, 455, 3448, 915,  1827, 488, 2171, 912,  3032, 495,  1827, 1741, 2348, 108, 3056, 914,  2024, 902,  1826, 1176, 3597, 237, 1832, 1547, 1889, 459,  3932, 918,  2165,
      110, 1946, 1002, 3422, 606, 1827, 1778, 1839, 228, 3469, 1097, 2364, 767,  1839, 923,  3068, 116, 1839, 2325, 1845, 459,  3632, 923,  1845, 380, 2621, 1022, 3503, 462,  1836, 1538, 1856,
      44,  3278, 905,  1850, 875, 1848, 926,  4133, 230, 1850, 1547, 2189, 506,  3683, 1190, 1854, 197, 2108, 926,  3092, 462,  2460, 2072, 1857, 233, 3143, 927,  1860, 1031, 1857, 956,  3884,
      60,  2231, 1556, 2391, 461, 3122, 939,  1863, 498, 1862, 1230, 3107, 551,  1863, 1553, 1881, 117, 4648, 1049, 1875, 797,  1862, 972,  3731, 299, 1863, 1765, 1871, 488,  3122, 938,  2784,
      23,  1871, 1118, 3672, 467, 2087, 2072, 1875, 228,
  });
  uint64_t s = 0;
  for (int i = 1; i <= n; ++i) {
    s += solutions[i];
  }
  printf("%lu\n", s);
}

int main() {
  int n;
  scanf("%d", &n);
  solve(n);
  return 0;
}