1503 19
0 1 2 1 1 4 1 5 5 6 1 2 9 4 8 15 13 13 12 8 10 17 4 18 14 17 6 23 8 28 29 22 1 33 7 3 22 23 21 16 20 12 31 16 35 34 4 22 5 42 20 14 45 48 48 41 43 25 5 34 51 27 3 5 20 28 61 7 8 67 62 46 51 7 31 74 50 4 15 73 12 19 59 10 47 67 66 82 55 23 11 89 11 59 62 60 18 94 50 15 19 55 36 27 11 27 98 20 52 86 105 64 32 111 98 110 112 101 75 54 26 79 102 96 79 51 64 24 13 125 31 23 1 3 43 8 61 107 32 129 94 7 9 112 144 110 101 21 145 110 37 132 52 45 10 60 133 71 23 62 147 139 32 111 60 60 140 88 82 55 115 72 26 137 89 15 119 82 16 42 145 141 121 121 164 96 44 92 171 175 3 68 167 20 2 63 69 159 21 16 114 118 133 42 37 63 195 45 127 172 208 156 75 207 181 184 109 156 94 99 86 112 74 149 53 202 148 46 68 125 178 82 219 225 173 17 153 152 211 111 115 204 85 96 43 167 65 22 24 29 217 58 17 58 8 6 225 106 192 61 47 2 58 143 2 135 171 203 241 237 228 170 47 171 28 69 275 257 75 153 130 8 193 47 127 52 39 184 12 181 210 124 12 70 83 149 110 252 104 148 15 82 186 86 22 127 273 130 269 254 33 244 212 249 74 63 255 7 142 4 6 168 238 51 27 200 198 169 60 76 27 301 177 236 143 278 150 256 6 113 63 217 199 302 222 42 128 314 113 111 58 194 18 223 235 243 331 308 92 137 56 158 194 195 90 135 207 339 62 358 271 216 86 101 163 253 334 81 360 203 333 262 346 199 364 87 152 342 36 139 66 75 27 36 359 375 382 198 59 287 230 134 324 23 176 75 237 391 384 407 33 351 119 36 99 227 261 357 371 363 153 97 310 117 30 165 419 32 305 364 206 180 253 6 38 362 61 7 271 401 340 345 91 333 373 180 193 107 119 216 43 380 9 296 143 368 140 358 25 112 205 73 91 107 430 312 289 181 178 44 25 360 101 416 281 287 124 216 214 39 267 249 10 10 184 44 143 261 376 246 425 119 414 129 32 172 340 249 84 329 447 91 287 482 382 229 70 398 171 141 424 58 68 263 275 505 197 69 472 342 276 184 25 494 524 231 126 176 178 364 148 360 419 522 491 172 254 229 66 208 370 526 293 140 340 492 255 1 403 261 340 241 94 15 485 251 278 194 270 291 322 226 415 282 79 501 41 235 55 182 162 126 46 427 264 499 119 416 61 161 470 272 503 75 283 65 220 212 454 518 475 483 530 315 463 112 493 506 269 118 475 470 202 52 392 162 558 130 247 74 218 460 151 317 192 7 28 600 213 72 420 386 174 573 190 307 43 316 205 389 103 60 577 169 622 377 197 273 415 255 122 226 166 146 210 239 291 275 166 102 89 557 568 430 566 342 70 573 657 596 66 497 326 88 2 465 454 206 435 432 208 4 608 514 197 592 313 344 311 136 332 537 105 552 335 172 671 138 316 542 210 102 133 117 108 90 496 513 195 206 696 389 677 158 290 122 455 654 668 334 48 495 662 117 11 124 356 384 418 540 655 127 683 407 553 128 565 334 205 269 248 45 476 92 694 549 256 519 26 537 292 530 741 573 504 274 139 186 479 23 616 245 55 743 609 600 112 15 465 37 680 113 726 491 110 266 311 689 607 28 394 92 238 333 59 750 368 161 232 436 251 694 448 416 466 8 352 152 483 347 213 466 459 545 461 390 157 667 716 721 702 83 668 242 349 350 761 648 225 481 689 138 5 790 808 161 494 201 593 276 120 684 319 33 764 781 559 765 31 253 3 653 178 712 418 57 248 530 115 412 770 253 36 470 656 616 4 485 527 132 486 796 408 840 219 523 487 209 18 217 244 119 465 32 841 132 330 374 209 144 571 585 347 396 790 313 844 346 622 744 352 553 804 79 827 590 430 762 550 684 311 864 442 624 425 113 632 603 553 256 110 401 780 640 376 259 762 765 886 18 411 109 24 561 855 687 508 845 470 566 789 211 804 369 725 197 243 58 480 836 79 707 613 396 436 410 749 915 309 883 287 650 265 161 645 20 1 454 653 426 344 93 19 430 538 700 94 237 535 599 460 427 405 718 59 815 398 786 492 54 588 267 583 924 43 265 970 748 891 942 57 770 761 488 193 371 635 112 678 53 1 501 662 296 802 722 117 295 754 236 397 427 24 862 489 697 537 432 644 633 20 368 589 790 436 462 315 544 498 405 246 759 170 353 626 441 128 322 702 406 764 310 660 822 638 486 448 520 910 753 197 272 122 29 487 978 1022 126 410 874 761 612 617 567 667 618 809 825 723 999 343 1055 642 674 550 167 240 739 486 558 118 133 441 1061 885 531 123 1043 747 835 999 376 278 200 830 463 907 67 987 123 1007 758 1068 553 933 416 386 652 424 509 694 762 668 155 157 1038 976 976 417 339 372 119 780 649 634 235 140 513 307 1116 538 423 826 261 477 790 773 619 858 37 467 211 823 1077 746 14 587 873 725 364 640 471 487 498 1096 220 208 1090 247 627 772 898 586 841 500 46 43 53 9 201 539 1156 927 44 146 999 198 717 439 79 752 353 247 195 12 32 1006 584 1127 127 82 1105 869 267 1003 951 180 658 912 1189 1022 365 253 318 825 106 1190 449 553 1033 311 578 27 565 118 100 764 573 891 179 862 407 992 342 495 575 1196 1158 1012 645 1004 434 663 222 1160 79 544 1196 41 869 47 628 960 785 1072 593 1152 616 519 700 438 259 275 427 609 196 883 288 1225 1070 952 580 542 1119 856 29 1070 132 354 132 1100 1041 1190 1247 538 96 1249 297 251 1122 456 230 53 1066 869 665 1253 995 614 1268 443 151 698 647 842 1234 103 1040 436 868 229 556 880 615 511 1207 1261 359 932 992 318 325 406 173 964 501 966 533 228 963 412 799 1211 669 34 548 832 181 286 1065 125 752 1020 348 447 309 532 103 308 315 93 553 1302 1052 850 75 928 685 1043 51 685 1326 73 594 229 1248 1214 445 927 689 905 624 697 1263 1026 745 609 754 1215 166 374 439 604 804 1137 1002 553 181 441 124 1275 1028 1049 544 472 1343 800 1354 507 472 436 1216 289 204 541 1121 189 500 388 396 525 530 903 1380 265 124 650 1185 251 619 723 313 53 409 47 62 441 597 708 1239 72 713 338 1224 1327 323 1274 998 55 568 545 303 1220 1268 710 130 684 534 303 125 1209 1139 813 82 427 1110 886 880 996 1020 1351 938 321 714 1018 240 349 511 1193 212 249 1105 392 1341 647 770 40 1427 533 1390 1142 709 1107 1152 1227 752 962 948 12 228 1047 643 553 181 1229 1076 65 793 195 306 918 28 1222 1306 607 1282 630 794 1299 490 421 323 237 877 969 273 1185 1084 1230 877 1152 1217 893