0 0 1 1 2 4 3 9 4 16 5 25 6 36 7 1 8 16 9 33 10 4 11 25 12 0 13 25 14 4 15 33 16 16 17 1 18 36 19 25 20 16 21 9 22 4 23 1 24 0 25 1 26 4 27 9 28 16 29 25 30 36 31 1 32 16 33 33 34 4 35 25 36 0 37 25 38 4 39 33 40 16 41 1 42 36 43 25 44 16 45 9 46 4 47 1 48 0 49 1 50 4 51 9 52 16 53 25 54 36 55 1 56 16 57 33 58 4 59 25 60 0 61 25 62 4 63 33 64 16 65 1 66 36 67 25 68 16 69 9 70 4 71 1 72 0 73 1 74 4 75 9 76 16 77 25 78 36 79 1 80 16 81 33 82 4 83 25 84 0 85 25 86 4 87 33 88 16 89 1 90 36 91 25 92 16 93 9 94 4 95 1 96 0 97 1 98 4 99 9 100 16 101 25 102 36 103 1 104 16 105 33 106 4 107 25 108 0 109 25 110 4 111 33 112 16 113 1 114 36 115 25 116 16 117 9 118 4 119 1 120 0 121 1 122 4 123 9 124 16 125 25 126 36 127 1 128 16 129 33 130 4 131 25 132 0 133 25 134 4 135 33 136 16 137 1 138 36 139 25 140 16 141 9 142 4 143 1 144 0 145 1 146 4 147 9 148 16 149 25 150 36 151 1 152 16 153 33 154 4 155 25 156 0 157 25 158 4 159 33 160 16 161 1 162 36 163 25 164 16 165 9 166 4 167 1 168 0 169 1 170 4 171 9 172 16 173 25 174 36 175 1 176 16 177 33 178 4 179 25 180 0 181 25 182 4 183 33 184 16 185 1 186 36 187 25 188 16 189 9 190 4 191 1 192 0 193 1 194 4 195 9 196 16 197 25 198 36 199 1 200 16 201 33 202 4 203 25 204 0 205 25 206 4 207 33 208 16 209 1 210 36 211 25 212 16 213 9 214 4 215 1 216 0 217 1 218 4 219 9 220 16 221 25 222 36 223 1 224 16 225 33 226 4 227 25 228 0 229 25 230 4 231 33 232 16 233 1 234 36 235 25 236 16 237 9 238 4 239 1 240 0 241 1 242 4 243 9 244 16 245 25 246 36 247 1 248 16 249 33 250 4 251 25 252 0 253 25 254 4 255 33 256 16 257 1 258 36 259 25 260 16 261 9 262 4 263 1 264 0 265 1 266 4 267 9 268 16 269 25 270 36 271 1 272 16 273 33 274 4 275 25 276 0 277 25 278 4 279 33 280 16 281 1 282 36 283 25 284 16 285 9 286 4 287 1 288 0 289 1 290 4 291 9 292 16 293 25 294 36 295 1 296 16 297 33 298 4 299 25 300 0 301 25 302 4 303 33 304 16 305 1 306 36 307 25 308 16 309 9 310 4 311 1 312 0 313 1 314 4 315 9 316 16 317 25 318 36 319 1 320 16 321 33 322 4 323 25 324 0 325 25 326 4 327 33 328 16 329 1 330 36 331 25 332 16 333 9 334 4 335 1 336 0 337 1 338 4 339 9 340 16 341 25 342 36 343 1 344 16 345 33 346 4 347 25 348 0 349 25 350 4 351 33 352 16 353 1 354 36 355 25 356 16 357 9 358 4 359 1 360 0 361 1 362 4 363 9 364 16 365 25 366 36 367 1 368 16 369 33 370 4 371 25 372 0 373 25 374 4 375 33 376 16 377 1 378 36 379 25 380 16 381 9 382 4 383 1 384 0 385 1 386 4 387 9 388 16 389 25 390 36 391 1 392 16 393 33 394 4 395 25 396 0 397 25 398 4 399 33 400 16 401 1 402 36 403 25 404 16 405 9 406 4 407 1 408 0 409 1 410 4 411 9 412 16 413 25 414 36 415 1 416 16 417 33 418 4 419 25 420 0 421 25 422 4 423 33 424 16 425 1 426 36 427 25 428 16 429 9 430 4 431 1 432 0 433 1 434 4 435 9 436 16 437 25 438 36 439 1 440 16 441 33 442 4 443 25 444 0 445 25 446 4 447 33 448 16 449 1 450 36 451 25 452 16 453 9 454 4 455 1 456 0 457 1 458 4 459 9 460 16 461 25 462 36 463 1 464 16 465 33 466 4 467 25 468 0 469 25 470 4 471 33 472 16 473 1 474 36 475 25 476 16 477 9 478 4 479 1 480 0 481 1 482 4 483 9 484 16 485 25 486 36 487 1 488 16 489 33 490 4 491 25 492 0 493 25 494 4 495 33 496 16 497 1 498 36 499 25 500 16 501 9 502 4 503 1 504 0 505 1 506 4 507 9 508 16 509 25 510 36 511 1 512 16 513 33 514 4 515 25 516 0 517 25 518 4 519 33 520 16 521 1 522 36 523 25 524 16 525 9 526 4 527 1 528 0 529 1 530 4 531 9 532 16 533 25 534 36 535 1 536 16 537 33 538 4 539 25 540 0 541 25 542 4 543 33 544 16 545 1 546 36 547 25 548 16 549 9 550 4 551 1 552 0 553 1 554 4 555 9 556 16 557 25 558 36 559 1 560 16 561 33 562 4 563 25 564 0 565 25 566 4 567 33 568 16 569 1 570 36 571 25 572 16 573 9 574 4 575 1 576 0 577 1 578 4 579 9 580 16 581 25 582 36 583 1 584 16 585 33 586 4 587 25 588 0 589 25 590 4 591 33 592 16 593 1 594 36 595 25 596 16 597 9 598 4 599 1 600 0 601 1 602 4 603 9 604 16 605 25 606 36 607 1 608 16 609 33 610 4 611 25 612 0 613 25 614 4 615 33 616 16 617 1 618 36 619 25 620 16 621 9 622 4 623 1 624 0 625 1 626 4 627 9 628 16 629 25 630 36 631 1 632 16 633 33 634 4 635 25 636 0 637 25 638 4 639 33 640 16 641 1 642 36 643 25 644 16 645 9 646 4 647 1 648 0 649 1 650 4 651 9 652 16 653 25 654 36 655 1 656 16 657 33 658 4 659 25 660 0 661 25 662 4 663 33 664 16 665 1 666 36 667 25 668 16 669 9 670 4 671 1 672 0 673 1 674 4 675 9 676 16 677 25 678 36 679 1 680 16 681 33 682 4 683 25 684 0 685 25 686 4 687 33 688 16 689 1 690 36 691 25 692 16 693 9 694 4 695 1 696 0 697 1 698 4 699 9 700 16 701 25 702 36 703 1 704 16 705 33 706 4 707 25 708 0 709 25 710 4 711 33 712 16 713 1 714 36 715 25 716 16 717 9 718 4 719 1 720 0 721 1 722 4 723 9 724 16 725 25 726 36 727 1 728 16 729 33 730 4 731 25 732 0 733 25 734 4 735 33 736 16 737 1 738 36 739 25 740 16 741 9 742 4 743 1 744 0 745 1 746 4 747 9 748 16 749 25 750 36 751 1 752 16 753 33 754 4 755 25 756 0 757 25 758 4 759 33 760 16 761 1 762 36 763 25 764 16 765 9 766 4 767 1 768 0 769 1 770 4 771 9 772 16 773 25 774 36 775 1 776 16 777 33 778 4 779 25 780 0 781 25 782 4 783 33 784 16 785 1 786 36 787 25 788 16 789 9 790 4 791 1 792 0 793 1 794 4 795 9 796 16 797 25 798 36 799 1 800 16 801 33 802 4 803 25 804 0 805 25 806 4 807 33 808 16 809 1 810 36 811 25 812 16 813 9 814 4 815 1 816 0 817 1 818 4 819 9 820 16 821 25 822 36 823 1 824 16 825 33 826 4 827 25 828 0 829 25 830 4 831 33 832 16 833 1 834 36 835 25 836 16 837 9 838 4 839 1 840 0 841 1 842 4 843 9 844 16 845 25 846 36 847 1 848 16 849 33 850 4 851 25 852 0 853 25 854 4 855 33 856 16 857 1 858 36 859 25 860 16 861 9 862 4 863 1 864 0 865 1 866 4 867 9 868 16 869 25 870 36 871 1 872 16 873 33 874 4 875 25 876 0 877 25 878 4 879 33 880 16 881 1 882 36 883 25 884 16 885 9 886 4 887 1 888 0 889 1 890 4 891 9 892 16 893 25 894 36 895 1 896 16 897 33 898 4 899 25 900 0 901 25 902 4 903 33 904 16 905 1 906 36 907 25 908 16 909 9 910 4 911 1 912 0 913 1 914 4 915 9 916 16 917 25 918 36 919 1 920 16 921 33 922 4 923 25 924 0 925 25 926 4 927 33 928 16 929 1 930 36 931 25 932 16 933 9 934 4 935 1 936 0 937 1 938 4 939 9 940 16 941 25 942 36 943 1 944 16 945 33 946 4 947 25 948 0 949 25 950 4 951 33 952 16 953 1 954 36 955 25 956 16 957 9 958 4 959 1 960 0 961 1 962 4 963 9 964 16 965 25 966 36 967 1 968 16 969 33 970 4 971 25 972 0 973 25 974 4 975 33 976 16 977 1 978 36 979 25 980 16 981 9 982 4 983 1 984 0 985 1 986 4 987 9 988 16 989 25 990 36 991 1 992 16 993 33 994 4 995 25 996 0 997 25 998 4 999 33 1000 16