1 2 2 3 3 5 4 7 5 13 6 11 7 19 8 17 9 29 10 23 11 37 12 43 13 31 14 47 15 41 16 61 17 53 18 67 19 71 20 59 21 73 22 89 23 79 24 83 25 103 26 101 27 107 28 109 29 97 30 127 31 131 32 113 33 139 34 137 35 151 36 157 37 149 38 163 39 173 40 181 41 191 42 167 43 193 44 211 45 179 46 199 47 223 48 197 49 227 50 233 51 239 52 229 53 241 54 257 55 251 56 277 57 293 58 283 59 313 60 281 61 271 62 307 63 269 64 337 65 263 66 311 67 347 68 317 69 359 70 353 71 367 72 331 73 373 74 379 75 349 76 389 77 383 78 401 79 397 80 421 81 409 82 443 83 431 84 419 85 449 86 433 87 439 88 467 89 457 90 463 91 491 92 487 93 479 94 523 95 461 96 509 97 499 98 541 99 503 100 521 101 557 102 547 103 569 104 563 105 571 106 587 107 577 108 601 109 607 110 599 111 593 112 613 113 617 114 631 115 653 116 619 117 643 118 647 119 659 120 677 121 673 122 661 123 641 124 701 125 691 126 719 127 709 128 727 129 733 130 743 131 739 132 751 133 757 134 761 135 773 136 797 137 769 138 683 139 811 140 787 141 809 142 827 143 823 144 829 145 863 146 853 147 859 148 839 149 881 150 857 151 883 152 877 153 887 154 907 155 911 156 821 157 941 158 947 159 937 160 953 161 971 162 977 163 967 164 929 165 919 166 991 167 997 168 983 169 1013 170 1021 171 1033 172 1031 173 1051 174 1019 175 1009 176 1039 177 1069 178 1063 179 1049 180 1061 181 1091 182 1087 183 1093 184 1117 185 1123 186 1097 187 1153 188 1109 189 1151 190 1163 191 1129 192 1103 193 1201 194 1217 195 1223 196 1171 197 1213 198 1231 199 1187 200 1229 201 1249 202 1237 203 1259 204 1193 205 1289 206 1283 207 1297 208 1279 209 1181 210 1291 211 1307 212 1303 213 1321 214 1301 215 1277 216 1367 217 1319 218 1381 219 1327 220 1409 221 1429 222 1423 223 1361 224 1373 225 1447 226 1427 227 1453 228 1471 229 1451 230 1487 231 1481 232 1439 233 1499 234 1433 235 1399 236 1489 237 1483 238 1511 239 1459 240 1493 241 1531 242 1523 243 1549 244 1567 245 1543 246 1553 247 1559 248 1571 249 1579 250 1597 251 1601 252 1607 253 1619 254 1613 255 1621 256 1637 257 1627 258 1657 259 1609 260 1663 261 1667 262 1693 263 1583 264 1669 265 1721 266 1699 267 1741 268 1697 269 1723 270 1747 271 1753 272 1783 273 1709 274 1759 275 1733 276 1787 277 1777 278 1789 279 1823 280 1811 281 1861 282 1867 283 1831 284 1871 285 1847 286 1801 287 1913 288 1877 289 1931 290 1873 291 1879 292 1933 293 1889 294 1901 295 1951 296 1949 297 1979 298 1987 299 1997 300 1993 301 1973 302 2011 303 2017 304 2053 305 1907 306 2029 307 2027 308 2063 309 2039 310 2081 311 2069 312 2087 313 2083 314 1999 315 2113 316 2003 317 2089 318 2129 319 2137 320 2141 321 2179 322 2131 323 2153 324 2111 325 2099 326 2213 327 2221 328 2207 329 2239 330 2237 331 2143 332 2243 333 2269 334 2161 335 2273 336 2287 337 2297 338 2267 339 2309 340 2293 341 2251 342 2281 343 2311 344 2203 345 2333 346 2339 347 2351 348 2381 349 2389 350 2393 351 2357 352 2341 353 2377 354 2347 355 2399 356 2423 357 2411 358 2371 359 2383 360 2447 361 2459 362 2467 363 2473 364 2441 365 2503 366 2417 367 2437 368 2543 369 2549 370 2531 371 2477 372 2521 373 2591 374 2539 375 2551 376 2609 377 2557 378 2579 379 2593 380 2621 381 2647 382 2633 383 2657 384 2663 385 2671 386 2707 387 2687 388 2693 389 2683 390 2729 391 2617 392 2699 393 2731 394 2719 395 2749 396 2711 397 2659 398 2689 399 2713 400 2777 401 2753 402 2677 403 2791 404 2801 405 2789 406 2837 407 2843 408 2861 409 2857 410 2741 411 2833 412 2803 413 2819 414 2879 415 2897 416 2767 417 2797 418 2903 419 2851 420 2909 421 2887 422 2963 423 2971 424 3023 425 3011 426 3019 427 3001 428 2939 429 2927 430 3049 431 3037 432 2999 433 2917 434 3041 435 2957 436 3079 437 2953 438 3089 439 3061 440 3121 441 3083 442 3109 443 3067 444 2969 445 3137 446 3119 447 3167 448 3187 449 3169 450 3181 451 3191 452 3221 453 3217 454 3163 455 3253 456 3259 457 3209 458 3251 459 3257 460 3299 461 3271 462 3301 463 3307 464 3313 465 3331 466 3203 467 3329 468 3323 469 3359 470 3373 471 3229 472 3361 473 3319 474 3407 475 3343 476 3391 477 3347 478 3433 479 3413 480 3389 481 3457 482 3469 483 3461 484 3467 485 3463 486 3499 487 3449 488 3511 489 3517 490 3527 491 3541 492 3529 493 3533 494 3547 495 3557 496 3371 497 3559 498 3583 499 3539 500 3571