0 0 1 1 2 1 3 6 4 4 5 13 6 9 7 22 8 16 9 33 10 25 11 46 12 36 13 61 14 49 15 78 16 64 17 97 18 81 19 118 20 100 21 141 22 121 23 166 24 144 25 193 26 169 27 222 28 196 29 253 30 225 31 286 32 256 33 321 34 289 35 358 36 324 37 397 38 361 39 438 40 400 41 481 42 441 43 526 44 484 45 573 46 529 47 622 48 576 49 673 50 625 51 726 52 676 53 781 54 729 55 838 56 784 57 897 58 841 59 958 60 900 61 1021 62 961 63 1086 64 1024 65 1153 66 1089 67 1222 68 1156 69 1293 70 1225 71 1366 72 1296 73 1441 74 1369 75 1518 76 1444 77 1597 78 1521 79 1678 80 1600 81 1761 82 1681 83 1846 84 1764 85 1933 86 1849 87 2022 88 1936 89 2113 90 2025 91 2206 92 2116 93 2301 94 2209 95 2398 96 2304 97 2497 98 2401 99 2598 100 2500 101 2701 102 2601 103 2806 104 2704 105 2913 106 2809 107 3022 108 2916 109 3133 110 3025 111 3246 112 3136 113 3361 114 3249 115 3478 116 3364 117 3597 118 3481 119 3718 120 3600 121 3841 122 3721 123 3966 124 3844 125 4093 126 3969 127 4222 128 4096 129 4353 130 4225 131 4486 132 4356 133 4621 134 4489 135 4758 136 4624 137 4897 138 4761 139 5038 140 4900 141 5181 142 5041 143 5326 144 5184 145 5473 146 5329 147 5622 148 5476 149 5773 150 5625 151 5926 152 5776 153 6081 154 5929 155 6238 156 6084 157 6397 158 6241 159 6558 160 6400 161 6721 162 6561 163 6886 164 6724 165 7053 166 6889 167 7222 168 7056 169 7393 170 7225 171 7566 172 7396 173 7741 174 7569 175 7918 176 7744 177 8097 178 7921 179 8278 180 8100 181 8461 182 8281 183 8646 184 8464 185 8833 186 8649 187 9022 188 8836 189 9213 190 9025 191 9406 192 9216 193 9601 194 9409 195 9798 196 9604 197 9997 198 9801 199 10198 200 10000 201 10401 202 10201 203 10606 204 10404 205 10813 206 10609 207 11022 208 10816 209 11233 210 11025 211 11446 212 11236 213 11661 214 11449 215 11878 216 11664 217 12097 218 11881 219 12318 220 12100 221 12541 222 12321 223 12766 224 12544 225 12993 226 12769 227 13222 228 12996 229 13453 230 13225 231 13686 232 13456 233 13921 234 13689 235 14158 236 13924 237 14397 238 14161 239 14638 240 14400 241 14881 242 14641 243 15126 244 14884 245 15373 246 15129 247 15622 248 15376 249 15873 250 15625 251 16126 252 15876 253 16381 254 16129 255 16638 256 16384 257 16897 258 16641 259 17158 260 16900 261 17421 262 17161 263 17686 264 17424 265 17953 266 17689 267 18222 268 17956 269 18493 270 18225 271 18766 272 18496 273 19041 274 18769 275 19318 276 19044 277 19597 278 19321 279 19878 280 19600 281 20161 282 19881 283 20446 284 20164 285 20733 286 20449 287 21022 288 20736 289 21313 290 21025 291 21606 292 21316 293 21901 294 21609 295 22198 296 21904 297 22497 298 22201 299 22798 300 22500 301 23101 302 22801 303 23406 304 23104 305 23713 306 23409 307 24022 308 23716 309 24333 310 24025 311 24646 312 24336 313 24961 314 24649 315 25278 316 24964 317 25597 318 25281 319 25918 320 25600 321 26241 322 25921 323 26566 324 26244 325 26893 326 26569 327 27222 328 26896 329 27553 330 27225 331 27886 332 27556 333 28221 334 27889 335 28558 336 28224 337 28897 338 28561 339 29238 340 28900 341 29581 342 29241 343 29926 344 29584 345 30273 346 29929 347 30622 348 30276 349 30973 350 30625 351 31326 352 30976 353 31681 354 31329 355 32038 356 31684 357 32397 358 32041 359 32758 360 32400 361 33121 362 32761 363 33486 364 33124 365 33853 366 33489 367 34222 368 33856 369 34593 370 34225 371 34966 372 34596 373 35341 374 34969 375 35718 376 35344 377 36097 378 35721 379 36478 380 36100 381 36861 382 36481 383 37246 384 36864 385 37633 386 37249 387 38022 388 37636 389 38413 390 38025 391 38806 392 38416 393 39201 394 38809 395 39598 396 39204 397 39997 398 39601 399 40398 400 40000 401 40801 402 40401 403 41206 404 40804 405 41613 406 41209 407 42022 408 41616 409 42433 410 42025 411 42846 412 42436 413 43261 414 42849 415 43678 416 43264 417 44097 418 43681 419 44518 420 44100 421 44941 422 44521 423 45366 424 44944 425 45793 426 45369 427 46222 428 45796 429 46653 430 46225 431 47086 432 46656 433 47521 434 47089 435 47958 436 47524 437 48397 438 47961 439 48838 440 48400 441 49281 442 48841 443 49726 444 49284 445 50173 446 49729 447 50622 448 50176 449 51073 450 50625 451 51526 452 51076 453 51981 454 51529 455 52438 456 51984 457 52897 458 52441 459 53358 460 52900 461 53821 462 53361 463 54286 464 53824 465 54753 466 54289 467 55222 468 54756 469 55693 470 55225 471 56166 472 55696 473 56641 474 56169 475 57118 476 56644 477 57597 478 57121 479 58078 480 57600 481 58561 482 58081 483 59046 484 58564 485 59533 486 59049 487 60022 488 59536 489 60513 490 60025 491 61006 492 60516 493 61501 494 61009 495 61998 496 61504 497 62497 498 62001 499 62998 500 62500 501 63501 502 63001 503 64006 504 63504 505 64513 506 64009 507 65022 508 64516 509 65533 510 65025 511 66046 512 65536 513 66561 514 66049 515 67078 516 66564 517 67597 518 67081 519 68118 520 67600 521 68641 522 68121 523 69166 524 68644 525 69693 526 69169 527 70222 528 69696 529 70753 530 70225 531 71286 532 70756 533 71821 534 71289 535 72358 536 71824 537 72897 538 72361 539 73438 540 72900 541 73981 542 73441 543 74526 544 73984 545 75073 546 74529 547 75622 548 75076 549 76173 550 75625 551 76726 552 76176 553 77281 554 76729 555 77838 556 77284 557 78397 558 77841 559 78958 560 78400 561 79521 562 78961 563 80086 564 79524 565 80653 566 80089 567 81222 568 80656 569 81793 570 81225 571 82366 572 81796 573 82941 574 82369 575 83518 576 82944 577 84097 578 83521 579 84678 580 84100 581 85261 582 84681 583 85846 584 85264 585 86433 586 85849 587 87022 588 86436 589 87613 590 87025 591 88206 592 87616 593 88801 594 88209 595 89398 596 88804 597 89997 598 89401 599 90598 600 90000 601 91201 602 90601 603 91806 604 91204 605 92413 606 91809 607 93022 608 92416 609 93633 610 93025 611 94246 612 93636 613 94861 614 94249 615 95478 616 94864 617 96097 618 95481 619 96718 620 96100 621 97341 622 96721 623 97966 624 97344 625 98593 626 97969 627 99222 628 98596 629 99853 630 99225 631 100486 632 99856 633 101121 634 100489 635 101758 636 101124 637 102397 638 101761 639 103038 640 102400 641 103681 642 103041 643 104326 644 103684 645 104973 646 104329 647 105622 648 104976 649 106273 650 105625 651 106926 652 106276 653 107581 654 106929 655 108238 656 107584 657 108897 658 108241 659 109558 660 108900 661 110221 662 109561 663 110886 664 110224 665 111553 666 110889 667 112222 668 111556 669 112893 670 112225 671 113566 672 112896 673 114241 674 113569 675 114918 676 114244 677 115597 678 114921 679 116278 680 115600 681 116961 682 116281 683 117646 684 116964 685 118333 686 117649 687 119022 688 118336 689 119713 690 119025 691 120406 692 119716 693 121101 694 120409 695 121798 696 121104 697 122497 698 121801 699 123198 700 122500 701 123901 702 123201 703 124606 704 123904 705 125313 706 124609 707 126022 708 125316 709 126733 710 126025 711 127446 712 126736 713 128161 714 127449 715 128878 716 128164 717 129597 718 128881 719 130318 720 129600 721 131041 722 130321 723 131766 724 131044 725 132493 726 131769 727 133222 728 132496 729 133953 730 133225 731 134686 732 133956 733 135421 734 134689 735 136158 736 135424 737 136897 738 136161 739 137638 740 136900 741 138381 742 137641 743 139126 744 138384 745 139873 746 139129 747 140622 748 139876 749 141373 750 140625 751 142126 752 141376 753 142881 754 142129 755 143638 756 142884 757 144397 758 143641 759 145158 760 144400 761 145921 762 145161 763 146686 764 145924 765 147453 766 146689 767 148222 768 147456 769 148993 770 148225 771 149766 772 148996 773 150541 774 149769 775 151318 776 150544 777 152097 778 151321 779 152878 780 152100 781 153661 782 152881 783 154446 784 153664 785 155233 786 154449 787 156022 788 155236 789 156813 790 156025 791 157606 792 156816 793 158401 794 157609 795 159198 796 158404 797 159997 798 159201 799 160798 800 160000 801 161601 802 160801 803 162406 804 161604 805 163213 806 162409 807 164022 808 163216 809 164833 810 164025 811 165646 812 164836 813 166461 814 165649 815 167278 816 166464 817 168097 818 167281 819 168918 820 168100 821 169741 822 168921 823 170566 824 169744 825 171393 826 170569 827 172222 828 171396 829 173053 830 172225 831 173886 832 173056 833 174721 834 173889 835 175558 836 174724 837 176397 838 175561 839 177238 840 176400 841 178081 842 177241 843 178926 844 178084 845 179773 846 178929 847 180622 848 179776 849 181473 850 180625 851 182326 852 181476 853 183181 854 182329 855 184038 856 183184 857 184897 858 184041 859 185758 860 184900 861 186621 862 185761 863 187486 864 186624 865 188353 866 187489 867 189222 868 188356 869 190093 870 189225 871 190966 872 190096 873 191841 874 190969 875 192718 876 191844 877 193597 878 192721 879 194478 880 193600 881 195361 882 194481 883 196246 884 195364 885 197133 886 196249 887 198022 888 197136 889 198913 890 198025 891 199806 892 198916 893 200701 894 199809 895 201598 896 200704 897 202497 898 201601 899 203398 900 202500 901 204301 902 203401 903 205206 904 204304 905 206113 906 205209 907 207022 908 206116 909 207933 910 207025 911 208846 912 207936 913 209761 914 208849 915 210678 916 209764 917 211597 918 210681 919 212518 920 211600 921 213441 922 212521 923 214366 924 213444 925 215293 926 214369 927 216222 928 215296 929 217153 930 216225 931 218086 932 217156 933 219021 934 218089 935 219958 936 219024 937 220897 938 219961 939 221838 940 220900 941 222781 942 221841 943 223726 944 222784 945 224673 946 223729 947 225622 948 224676 949 226573 950 225625 951 227526 952 226576 953 228481 954 227529 955 229438 956 228484 957 230397 958 229441 959 231358 960 230400 961 232321 962 231361 963 233286 964 232324 965 234253 966 233289 967 235222 968 234256 969 236193 970 235225 971 237166 972 236196 973 238141 974 237169 975 239118 976 238144 977 240097 978 239121 979 241078 980 240100 981 242061 982 241081 983 243046 984 242064 985 244033 986 243049 987 245022 988 244036 989 246013 990 245025 991 247006 992 246016 993 248001 994 247009 995 248998 996 248004 997 249997 998 249001 999 250998 1000 250000