Input: 418
71 145 400 201 80 164 264 290 136 202 337 95 129 210 84 275 174 68 72 338 350 128 22 94 327 160 61 209 154 168 192 14 274 165 231 208 322 320 146 242 184 148 73 2 399 78 106 250 21 29 90 276 119 152 414 335 297 302 27 254 268 36 170 234 42 18 291 188 354 141 19 195 81 38 135 306 325 284 355 5 217 411 155 76 20 324 115 17 153 159 286 166 60 349 47 23 99 206 312 352 259 32 74 105 253 117 403 376 13 179 303 156 415 381 199 251 157 224 265 416 69 246 260 55 315 225 281 271 207 167 180 87 110 248 270 59 247 357 393 262 26 367 40 53 100 124 103 118 64 85 307 176 370 245 28 305 299 296 361 102 191 402 344 387 310 198 56 218 404 279 66 33 343 273 228 348 77 3 215 332 111 375 7 226 101 205 97 334 257 328 131 150 151 256 177 49 58 41 407 194 358 374 123 133 319 236 109 326 397 144 238 395 211 9 359 187 406 137 386 31 182 356 363 330 331 380 313 417 369 280 46 391 178 311 269 366 10 372 383 277 316 163 339 4 169 196 287 37 285 25 130 82 185 398 161 104 240 16 70 121 323 289 98 89 62 309 227 175 138 301 229 120 333 75 186 35 329 116 44 134 342 34 346 142 172 140 67 377 347 379 292 364 149 314 193 91 162 304 371 216 241 48 1 113 96 221 396 230 24 360 294 394 261 112 51 11 143 341 389 147 249 12 388 173 50 88 293 300 183 412 43 220 321 378 222 266 158 204 45 127 139 30 244 243 203 267 213 410 390 189 57 235 401 405 92 408 382 200 345 212 272 126 114 197 392 263 239 65 351 132 125 418 93 340 86 255 6 237 385 54 63 288 278 171 39 368 8 15 219 373 336 353 409 384 318 308 252 181 282 122 52 317 298 362 83 107 233 190 108 223 283 214 365 295 258 413 232
Output: 79