1 0 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 11 89 12 0 13 64 14 181 15 160 16 219 17 152 18 316 19 210 20 365 21 362 22 287 23 91 24 288 25 25 26 389 27 317 28 291 29 378 30 440 31 869 32 261 33 574 34 339 35 765 36 432 37 443 38 533 39 1285 40 1355 41 1641 42 1504 43 85 44 1741 45 20 46 551 47 1832 48 576 49 1457 50 1525 51 389 52 803 53 2066 54 332 55 1820 56 245 57 2149 58 2263 59 296 60 720 61 1465 62 1365 63 1114 64 187 65 190 66 316 67 2009 68 813 69 1631 70 3935 71 4474 72 4320 73 3211 74 5401 75 4925 76 1523 77 4930 78 5660 79 5057 80 485 81 3652 82 6479 83 2572 84 6912 85 1185 86 4213 87 6208 88 2859 89 4184 90 7120 91 2028 92 2573 93 7535 94 6579 95 4280 96 1152 97 2909 98 7757 99 452 100 5075 101 10000 102 332 103 9475 104 8533 105 8980 106 6783 107 10164 108 1296 109 1418 110 605 111 5326 112 6811 113 9378 114 3808 115 2410 116 8877 117 9443 118 1771 119 6481 120 1440 121 9043 122 8785 123 9596 124 8931 125 125 126 8756 127 7238 128 10949 129 6577 130 8915 131 4193 132 3312 133 6340 134 3081 135 9565 136 13579 137 14795 138 9928 139 17793 140 9405 141 4322 142 6675 143 574 144 8640 145 3920 146 8613 147 11153 148 20643 149 8941 150 15200 151 4531 152 629 153 20230 154 20859 155 23720 156 3600 157 21194 158 5373 159 24802 160 15995 161 11257 162 25912 163 13528 164 8941 165 7265 166 1659 167 24214 168 14112 169 22582 170 285 171 1478 172 28291 173 18683 174 10448 175 6700 176 13989 177 61 178 25099 179 15574 180 2160 181 28237 182 23829 183 13849 184 17643 185 31260 186 32248 187 10859 188 24813 189 33203 190 29695 191 8978 192 2304 193 15632 194 36277 195 33905 196 3923 197 5515 198 16532 199 20299 200 29525 201 24118 202 19191 203 10946 204 29232 205 6155 206 35637 207 2059 208 37467 209 20780 210 33580 211 11817 212 1693 213 8309 214 38091 215 32460 216 44064 217 34950 218 32265 219 27884 220 38115 221 39275 222 20564 223 24529 224 7301 225 25225 226 30735 227 34049 228 19296 229 2062 230 28465 231 31912 232 45899 233 23765 234 30124 235 34540 236 29149 237 41951 238 43007 239 29159 240 2880 241 21932 242 10209 243 51995 244 40995 245 1195 246 56096 247 58791 248 18869 249 51541 250 1375 251 31376 252 35424 253 10859 254 43433 255 23020 256 11323 257 65791 258 9280 259 35359 260 18845 261 1397 262 59475 263 20776 264 14688 265 15365 266 56237 267 26435 268 47299 269 43848 270 23660 271 27101 272 61029 273 10816 274 13699 275 8475 276 76032 277 29638 278 29469 279 66157 280 54635 281 69127 282 38908 283 44996 284 34509 285 29585 286 66503 287 53887 288 58752 289 74699 290 26445 291 44327 292 36643 293 29592 294 84932 295 16230 296 27285 297 69181 298 9239 299 15062 300 39600 301 6351 302 27181 303 17980 304 63003 305 6105 306 8092 307 20261 308 55373 309 28838 310 68255 311 13996 312 65952 313 44445 314 28573 315 78860 316 41715 317 73543 318 65924 319 66760 320 42565 321 87631 322 4131 323 1293 324 3888 325 7200 326 81173 327 40768 328 8139 329 38527 330 41140 331 68849 332 99597 333 44921 334 89511 335 20765 336 84672 337 86945 338 50649 339 48701 340 70755 341 71358 342 15884 343 85665 344 50805 345 51370 346 112103 347 41292 348 104544 349 19196 350 51925 351 84733 352 23035 353 100957 354 59716 355 119995 356 37917 357 24176 358 93439 359 45594 360 47520 361 8152 362 38373 363 52967 364 1859 365 123365 366 24164 367 120742 368 99109 369 2248 370 39535 371 37564 372 125136 373 1118 374 71437 375 62125 376 141355 377 137461 378 133804 379 88308 380 84285 381 6221 382 53863 383 55534 384 4608 385 42960 386 93797 387 75431 388 62659 389 124481 390 118520 391 107768 392 39445 393 33145 394 33095 395 90855 396 142128 397 96073 398 121789 399 96370 400 19675 401 108271 402 55468 403 70913 404 14749 405 32555 406 130355 407 135368 408 12384 409 77302 410 84105 411 27398 412 159235 413 77303 414 139004 415 141510 416 47109 417 136222 418 109823 419 66203 420 98640 421 15999 422 70897 423 18907 424 35595 425 139175 426 39484 427 55340 428 147229 429 175781 430 124215 431 55169 432 88128 433 81403 434 27161 435 27290 436 87203 437 134601 438 48464 439 176479 440 73205 441 139516 442 85259 443 141759 444 138384 445 32045 446 47721 447 151684 448 96187 449 51636 450 175600 451 39777 452 7229 453 54362 454 204299 455 38870 456 188640 457 8225 458 117249 459 112421 460 64995 461 14753 462 188684 463 209738 464 135141 465 173590 466 142595 467 212017 468 176688 469 8496 470 155985 471 32497 472 103979 473 153034 474 71740 475 37025 476 62717 477 48620 478 60707 479 90053 480 5760 481 655 482 15425 483 11594 484 118627 485 18910 486 79064 487 48212 488 74197 489 2932 490 14195 491 16204 492 124128 493 118902 494 82937 495 6055 496 145819 497 106513 498 29872 499 215569 500 44125 501 67466 502 188251 503 13077 504 211680 505 90905 506 33349 507 242075 508 234947 509 72788 510 233180 511 17872 512 33221 513 19528 514 130555 515 149860 516 154656 517 36148 518 199053 519 224206 520 144715 521 128167 522 246880 523 20396 524 14413 525 18650 526 262999 527 262152 528 188352 529 143797 530 267065 531 194852 532 192867 533 215073 534 166616 535 43865 536 226037 537 58714 538 263083 539 7712 540 6480 541 154727 542 162601 543 207790 544 269691 545 137345 546 280540 547 45400 548 113981 549 67439 550 154275 551 299111 552 152352 553 240015 554 177833 555 27695 556 189043 557 110285 558 9404 559 101505 560 59045 561 267136 562 256835 563 252786 564 243504 565 196615 566 269981 567 82627 568 58667 569 201996 570 172360 571 270655 572 286573 573 326612 574 269583 575 319425 576 117504 577 170214 578 237797 579 113096 580 100435 581 115855 582 13184 583 100399 584 67285 585 215035 586 5859 587 65156 588 310608 589 309686 590 154045 591 182617 592 221531 593 19568 594 238780 595 253605 596 117117 597 243578 598 25899 599 139568 600 79200 601 158064 602 27229 603 41573 604 309251 605 9080 606 345428 607 215484 608 249733 609 131209 610 237955 611 258549 612 249696 613 53943 614 310069 615 19060 616 241227 617 364646 618 259552 619 54473 620 143165 621 144902 622 83971 623 326376 624 383040 625 313125 626 70737 627 133553 628 248371 629 345796 630 167840 631 90234 632 103669 633 364399 634 39307 635 398140 636 99072 637 370617 638 40853 639 201319 640 279355 641 165379 642 273484 643 282276 644 78893 645 150320 646 409563 647 234213 648 412128 649 71479 650 89825 651 38288 652 219395 653 55504 654 153044 655 316370 656 425829 657 209257 658 386527 659 33610 660 87120 661 149387 662 413089 663 256732 664 361195 665 254715 666 269884 667 149413 668 120237 669 45713 670 272635 671 339615 672 395136 673 424662 674 294537 675 86825 676 232755 677 415677 678 451088 679 44995 680 419285 681 408598 682 407815 683 210363 684 155952 685 156860 686 366113 687 129616 688 206875 689 151188 690 260920 691 52517 692 44285 693 418871 694 6939 695 302330 696 129888 697 345095 698 358773 699 13745 700 334275 701 247454 702 318176 703 391534 704 380229 705 203605 706 107311 707 81419 708 221040 709 50340 710 259205 711 200536 712 162891 713 477010 714 68536 715 157910 716 371965 717 178535 718 273559 719 73339 720 354240 721 141303 722 56849 723 88931 724 266435 725 478850 726 292652 727 217372 728 505141 729 508606 730 167115 731 149247 732 298800 733 268277 734 185701 735 72115 736 188667 737 314811 738 95572 739 124153 740 282205 741 149798 742 51563 743 26747 744 421344 745 269695 746 6713 747 147872 748 108371 749 323234 750 363500 751 344710 752 11045 753 502504 754 150799 755 21145 756 557280 757 264949 758 242561 759 232288 760 345195 761 252653 762 201160 763 406474 764 178397 765 291890 766 39831 767 38465 768 304128 769 249926 770 324885 771 261110 772 214227 773 356352 774 554696 775 581100 776 134421 777 474235 778 444239 779 373222 780 347760 781 309365 782 372517 783 563848 784 9947 785 179760 786 590032 787 280958 788 154445 789 525998 790 352395 791 537641 792 125280 793 300841 794 261225 795 450155 796 251539 797 549132 798 594404 799 166052 800 638725 801 437380 802 328019 803 257820 804 9504 805 222430 806 348561 807 453805 808 148491 809 162610 810 603280 811 343054 812 138765 813 104879 814 489855 815 212710 816 403776 817 369145 818 129245 819 113906 820 193315 821 449909 822 321668 823 59255 824 274165 825 202075 826 168055 827 122395 828 152496 829 325798 830 202465 831 585853 832 179899 833 307756 834 685000 835 76815 836 384733 837 673508 838 46091 839 159411 840 211680 841 622718 842 95989 843 118865 844 330851 845 69945 846 256292 847 10375 848 674021 849 539962 850 422175 851 461038 852 225072 853 504122 854 519121 855 614095 856 616299 857 498773 858 543124 859 177814 860 366045 861 712784 862 702531 863 308953 864 176256 865 279390 866 113445 867 333695 868 682867 869 564070 870 184760 871 294634 872 627861 873 202696 874 718483 875 733500 876 388800 877 360446 878 287985 879 97567 880 52635 881 325971 882 499276 883 437084 884 761565 885 379685 886 65563 887 462126 888 38880 889 421119 890 392545 891 287948 892 587379 893 357954 894 166292 895 375905 896 612549 897 263914 898 309811 899 454461 900 658800 901 748936 902 464201 903 737512 904 155467 905 570155 906 398044 907 185934 908 541165 909 422921 910 506155 911 453679 912 331200 913 258788 914 467053 915 688385 916 267475 917 336159 918 740996 919 453068 920 168565 921 243142 922 513555 923 649741 924 49536 925 779675 926 400957 927 201022 928 303227 929 321435 930 38440 931 410405 932 231133 933 167942 934 399751 935 22390 936 750816 937 162100 938 746941 939 337412 940 752755 941 2824 942 317132 943 486299 944 873125 945 129445 946 548083 947 172353 948 364176 949 827660 950 95225 951 279592 952 775915 953 544162 954 748108 955 676145 956 16733 957 99794 958 81431 959 375915 960 11520 961 807148 962 851633 963 667325 964 381747 965 673565 966 104336 967 148917 968 226709 969 850138 970 850635 971 34957 972 641520 973 559071 974 289277 975 335275 976 258651 977 581314 978 504640 979 269314 980 873085 981 695999 982 97219 983 898461 984 93600 985 885510 986 122301 987 243794 988 574179 989 937682 990 546920 991 57479 992 293509 993 387934 994 646619 995 522380 996 848448 997 249249 998 297405 999 747637 1000 228875