1000
99225 518400 696423 1296 659344 64516 375769 781616 844561 799236 5041 91809 443556 1849 492804 22801 655836 33856 361355 17424 104862 38025 43681 877969 565504 837225 198025 370881 334084 16900 422500 819025 47961 652864 434281 77284 28044 571940 976144 44944 226576 690561 284089 86436 893714 809401 116964 137641 290521 22801 123904 278784 53824 958441 323761 938435 256 112225 585543 7921 594441 31684 9409 9409 695556 401956 521284 358801 373321 802816 544644 6724 750275 399424 239121 18225 792100 425104 379483 128376 283055 35344 13225 30276 134689 388129 47524 863041 805050 4624 240100 855625 448289 712336 234451 737944 496111 14113 393129 258064 613089 781871 223588 974169 120409 595911 113422 49729 848241 391270 992016 81225 302500 292681 26896 26569 811801 546121 136161 36481 73984 9216 454276 769129 5776 413449 200704 12773 10404 966047 580069 585294 913510 784 698896 178084 69696 770884 366025 348100 91586 208849 240384 374544 786769 304704 382446 693889 300304 837225 138384 664834 531441 437709 828700 456976 256 5625 98596 717686 447561 514089 298116 123904 9 632025 853776 48841 495462 135495 709331 541696 436921 303601 287099 714025 31329 217156 69696 133225 282456 839056 573049 50176 710928 79524 40401 685699 925576 374544 323761 538915 36864 612262 322624 304704 469225 152100 77284 248880 491401 660969 261121 376909 509796 19600 772641 698896 641601 553536 556516 447561 477481 6241 683929 794239 401831 21904 487204 656100 627264 95481 715716 16900 625 254016 320356 812991 302500 191844 114128 677329 687447 225060 877969 147456 144400 104329 835922 635209 787293 32761 195364 191298 81225 940900 42025 469225 309080 164201 418609 123201 40401 998001 98596 1000000 15129 550564 46656 806395 662695 405769 68121 495616 792100 433530 250000 1600 116964 389376 364816 802816 77841 13456 362404 214369 758641 829589 108452 463257 573049 910116 35721 1369 19321 70756 559744 116281 640000 5184 356409 264196 343396 252004 148996 128164 14400 918131 562500 894916 515524 55696 1764 921600 4096 239121 11664 729814 254016 487204 185761 881721 725904 568516 31329 277629 35344 47524 802816 770884 4900 239121 614656 91809 388129 705600 8836 98596 31329 193600 582169 384400 147456 534763 497025 321489 754959 23409 400 324 480680 570025 52900 36671 810769 518400 257432 337993 885481 391701 579121 4225 777763 2116 466489 101428 10609 731025 841930 556201 576 958441 29929 602176 315844 332336 85849 99225 13456 3136 2401 36481 454416 603729 257049 123201 693889 710687 293764 779689 877969 63001 32761 207191 195364 11664 201601 4624 75625 770988 21352 3364 638401 902500 978121 80089 2401 855625 38416 972191 90000 859071 917764 176141 269361 451584 518400 565953 659157 276676 4096 616225 74529 620944 738360 13225 52441 131353 132496 483025 295936 826058 674110 864900 6400 168100 184960 454602 40401 71244 190096 715950 817216 18769 802816 620944 516396 860539 409600 7056 346921 741321 401956 291600 10404 467856 1521 825969 492791 49729 1521 749086 116281 450241 96100 846400 288369 511225 175561 403225 57600 147456 469225 52888 129108 968256 640862 921640 435091 36481 416025 633116 83870 534361 166073 200 600625 207025 426409 38025 30625 54756 247009 405769 614656 3969 861184 49141 321214 278784 412164 593706 131769 654481 213477 913936 824232 748225 856777 369664 164836 343396 763444 283024 5184 652864 219024 126736 652864 471969 748225 58451 962361 21609 343396 674041 962361 652401 243783 613089 555821 914807 281991 668179 933156 270400 918350 516961 37636 3964 604029 856670 744769 574564 66564 748415 616225 490000 317779 399132 400 101124 307782 8649 915849 15376 124609 290851 20795 974169 320356 19600 429015 263591 549081 80089 266256 115887 940900 16641 321578 2401 231361 63504 206039 884076 308025 546121 234656 149769 57600 905440 272484 715716 92416 7921 96721 69696 32041 99856 18769 1000000 22801 553536 755161 583696 687241 91204 648025 825932 201218 534361 946729 822649 23716 441 954529 75076 315844 22801 447561 731025 714025 746496 153885 157609 971143 480249 3364 532798 207756 483025 3249 143641 97969 134689 400 305809 225 440896 403225 314721 2209 92416 28561 64909 34528 41209 824397 611524 219024 148996 149769 50625 499849 614204 727609 77284 655653 873677 62001 863478 722144 974169 491493 138384 662596 11449 624100 400689 410881 799236 872003 365715 900601 194747 518400 67081 487204 454276 906304 613089 83521 861184 110224 91204 329476 974169 174724 804609 246016 23716 472204 1764 874826 22500 337561 570025 221841 154066 400689 23104 144 19600 980100 403977 938961 181476 274576 97969 386134 77841 13225 191844 786769 104329 43681 576 214369 287296 499849 617181 950899 285156 476644 426516 41949 485809 408321 13456 302500 6400 256036 538918 478947 896809 7225 1681 85264 295369 933156 784996 16129 702320 308025 64009 504948 687241 829921 990025 114921 284089 408644 770731 70756 592054 303601 961 191220 544644 37636 702433 850084 654481 225 307585 8100 270400 499849 248004 767988 9216 6241 817216 29929 338724 693889 844561 9801 109561 28224 636051 109286 767376 786769 374544 38809 394384 292681 227529 190969 128164 220900 32041 146689 17689 232324 53824 62500 294849 495616 972196 558009 956484 3136 15129 599076 263169 592900 169 123904 309136 17424 8836 837225 253009 10000 479284 349281 235225 671923 187489 14161 93636 245025 99856 21025 94864 794487 592900 778504 556516 753424 980100 879844 863931 116281 47089 34969 234256 398161 173415 20449 863041 212997 529184 553536 463048 303601 948676 5929 625681 366025 674334 367236 206116 332929 990025 660261 374544 164836 119716 915780 298116 269361 382805 70225 396900 396900 465124 617796 929296 115600 289 108241 47961 974400 567216 9216 399424 370812 2401 93636 888166 917764 80656 110684 915849 131044 9409 514089 640000 857476 59141 15625 110889 885481 120409 695556 393129 11025 412164 1000000 110889 11881 948676 207936 657756 864900 187489 682166 2809 792100 891136 625681 409600 693889 312485 235707 255025 859329 832897 896809 95205 473344 53617 561444 702757 55225 77841 519841 355064 443556 53125 69169 683929 527089 374544 20449 246491 781379 393129 31684 129600 556516 82239 519841 701271 484 900 38025 153664 614656 972196 959822 126025 246016 10537 538595 306916 375081 398161 68644 893025 779689 91874 478763 648996 630436 3249 535824 544644 254951 679138 229441 97108 244790 26244 62500 1764 319225 46656 29929 132759 646416 710649 174357 68121 668446 269361 561001 108241 203401 380689 407044 514064 283024 609961 595984 274576 57121 155663 12769 66049 99856 772641 941325 116876 600924 31684 4489 438244 2199 162409 2704 512656 65025 594441 378225 842724