input (14000B)
1 68878 98732 2 24519 87903 3 73275 70114 4 87985 89419 5 80485 75440 6 98994 55979 7 28041 41805 8 50762 92905 9 23796 72412 10 71699 84915 11 43168 71645 12 12985 96078 13 38491 34431 14 30867 76208 15 89794 10790 16 59797 86225 17 62401 50098 18 90230 45208 19 40596 36238 20 52821 75949 21 61994 85771 22 62756 70340 23 91145 33842 24 57051 45050 25 36257 80983 26 36465 84670 27 98498 23292 28 49344 50098 29 13100 22817 30 82572 57598 31 77578 36555 32 99900 91029 33 75949 26486 34 50711 74711 35 52402 27513 36 69977 71045 37 23803 41588 38 57399 16399 39 81372 45126 40 98985 10547 41 76606 99481 42 86993 78240 43 54958 27513 44 23734 61444 45 25189 10790 46 11983 91029 47 53266 91029 48 31226 16399 49 54686 86915 50 60013 40760 51 29568 52436 52 97354 44827 53 91545 40986 54 15914 60707 55 64854 49298 56 30497 66916 57 39169 92811 58 13341 98568 59 89066 41215 60 89654 33815 61 59655 66645 62 89071 48550 63 91777 41832 64 28820 23803 65 68277 10790 66 24747 20641 67 19058 68263 68 50952 65659 69 77247 71079 70 79147 28383 71 89104 79596 72 26384 27513 73 58111 79657 74 61032 72412 75 45514 49298 76 37369 80983 77 66897 96745 78 42256 18346 79 53662 67789 80 18203 50098 81 14178 24879 82 16119 50862 83 85457 55460 84 74217 62672 85 72612 50061 86 30548 32091 87 21631 49298 88 55905 19836 89 15340 92089 90 44619 28383 91 67975 95646 92 22169 56053 93 15778 32810 94 63133 98314 95 42385 35192 96 51645 87903 97 30068 80881 98 44510 83025 99 50757 59248 100 31854 16399 101 54593 27981 102 16570 11600 103 21295 99780 104 70191 38799 105 64847 16732 106 30348 30596 107 92301 49298 108 66545 23803 109 32957 27513 110 49572 10507 111 10790 65414 112 85781 24738 113 32819 50098 114 22674 23803 115 44321 40307 116 39258 19836 117 25314 27018 118 98446 83025 119 96722 15026 120 96131 51435 121 60029 46857 122 22672 24485 123 57347 40735 124 55089 65268 125 93093 57076 126 46410 40686 127 46719 49999 128 48860 80891 129 75752 40285 130 32025 76676 131 58831 14816 132 93208 75949 133 93404 87903 134 91034 54811 135 74178 40675 136 99272 84920 137 24617 59248 138 31004 22425 139 49824 79823 140 50187 76234 141 64360 55010 142 40773 10935 143 93193 28383 144 24292 27513 145 66603 96899 146 94711 49904 147 81183 59248 148 38727 50143 149 47093 34542 150 94395 41907 151 39003 89663 152 40029 57072 153 90456 84416 154 75830 87903 155 33466 27513 156 16427 59248 157 49490 33354 158 52134 40307 159 67069 80983 160 35192 57341 161 82716 11017 162 74969 49298 163 16596 30045 164 30786 50769 165 69766 39818 166 88136 94929 167 29630 70754 168 98865 52818 169 83025 52968 170 38613 75675 171 34339 87903 172 20221 11583 173 60785 21075 174 42016 32352 175 50862 54811 176 91144 10790 177 82759 92299 178 34668 35814 179 80045 80983 180 17106 87903 181 47417 28383 182 62403 75949 183 58496 77896 184 98013 75949 185 82894 34330 186 93384 44962 187 95803 10790 188 76669 66543 189 14186 80983 190 40149 58549 191 50049 40735 192 62487 55256 193 32816 59248 194 84420 67838 195 54052 83025 196 91698 73884 197 62982 26639 198 34047 65346 199 32974 19836 200 36970 14966 201 14307 18019 202 26904 87903 203 36343 72547 204 43235 89108 205 76676 72412 206 55938 66916 207 34071 16143 208 72820 64337 209 17369 17215 210 46104 45050 211 88124 73288 212 31485 52329 213 50048 87903 214 11820 51419 215 81418 69376 216 45029 97736 217 10581 25449 218 49081 33618 219 52159 99078 220 81831 98314 221 88990 32303 222 43609 44962 223 32213 40285 224 40285 83782 225 99022 50098 226 53784 22929 227 88877 40307 228 50928 58596 229 41715 92182 230 88640 20046 231 57029 69964 232 47786 36174 233 85810 15842 234 11369 90510 235 70368 27513 236 94570 64489 237 39889 80581 238 13275 16427 239 68274 27513 240 77936 51774 241 15466 29702 242 44729 80983 243 32438 16399 244 41087 23803 245 60462 49298 246 65311 76326 247 32702 40735 248 82433 97292 249 93862 90212 250 33210 81930 251 94761 90283 252 42167 74463 253 35098 48550 254 27078 99873 255 54429 12606 256 27075 89108 257 97224 73884 258 56433 68263 259 30526 59248 260 40340 10790 261 69964 48550 262 58197 72412 263 86344 18262 264 28455 87594 265 87168 57559 266 73594 65764 267 43616 54811 268 36860 55905 269 62313 46800 270 63659 87903 271 19649 40735 272 63386 45583 273 70670 96410 274 25427 84151 275 95907 50098 276 90333 92116 277 88441 40735 278 52924 40735 279 54606 93929 280 53431 35192 281 72778 94800 282 32259 44962 283 22837 15734 284 41370 20407 285 50667 91029 286 23172 20736 287 87478 78442 288 18679 67415 289 25132 27513 290 35955 72412 291 19951 42485 292 92404 73884 293 43932 75949 294 89428 47755 295 68629 23255 296 18060 75949 297 96741 67071 298 46707 89108 299 89112 92197 300 55083 71071 301 41640 66916 302 17099 58116 303 70851 16399 304 23057 92148 305 19836 92356 306 25812 72833 307 93063 23164 308 45392 59203 309 21796 69964 310 97556 35192 311 57076 97029 312 58339 50098 313 58116 62171 314 91036 98314 315 60829 59813 316 22495 46432 317 66493 29832 318 15341 17977 319 50093 59248 320 20768 10238 321 23220 40987 322 51196 62761 323 23277 80983 324 37255 28383 325 42832 93721 326 60978 28336 327 81525 16486 328 75180 66916 329 69316 49298 330 29241 48253 331 11596 50862 332 34351 31482 333 43881 52947 334 18039 15790 335 35090 47718 336 37781 66916 337 90037 44975 338 58775 49298 339 11066 92303 340 35717 97563 341 73565 49309 342 26674 96015 343 91767 35192 344 20613 29701 345 98660 26456 346 19235 73884 347 52519 61051 348 40366 14356 349 33606 59248 350 67433 78913 351 51982 98675 352 21129 45050 353 26259 59939 354 41424 74011 355 15544 18046 356 85842 93362 357 44238 54811 358 50995 77228 359 50211 45766 360 88522 55008 361 85664 10790 362 83872 49541 363 90863 66681 364 12731 80983 365 35092 44962 366 89343 27513 367 43030 59369 368 14341 14679 369 67832 54811 370 65399 97833 371 40649 53538 372 99865 39569 373 84679 16399 374 37678 91006 375 40703 80889 376 36214 88977 377 38351 87638 378 41150 30413 379 82746 40735 380 34606 89108 381 32107 18123 382 35459 50816 383 26610 23803 384 18202 49298 385 34659 23803 386 89860 35192 387 25591 72412 388 11117 92839 389 90319 83025 390 36871 40735 391 94581 72076 392 56790 46209 393 13136 81739 394 12085 62323 395 75208 37298 396 80354 40735 397 61593 39732 398 21371 71180 399 44422 19479 400 37274 27513 401 13294 41590 402 12424 22554 403 57230 40809 404 95559 81507 405 18733 43631 406 95220 79915 407 15071 92369 408 70964 57296 409 55914 83712 410 57268 87903 411 61644 20006 412 14409 58116 413 19343 90069 414 79716 73884 415 57337 79683 416 35640 48701 417 65868 66918 418 21687 49298 419 90364 90368 420 81563 96307 421 99862 35192 422 50098 23985 423 56421 33574 424 87642 50862 425 80261 57845 426 80290 53468 427 69199 73884 428 52657 73884 429 82897 13916 430 55530 23966 431 77782 54811 432 60975 11030 433 99943 66089 434 14928 40735 435 32910 50078 436 73884 52473 437 81361 58116 438 13203 16427 439 72163 80438 440 82198 13938 441 46030 38491 442 33431 52909 443 30199 40285 444 58012 61365 445 60604 88325 446 66916 73884 447 59248 10790 448 52823 68263 449 67584 38374 450 35764 58969 451 38010 35192 452 53537 27513 453 40680 90231 454 77944 85142 455 65080 80983 456 15342 65310 457 66994 49661 458 46267 41636 459 80983 95143 460 78052 36273 461 54944 49284 462 37652 65872 463 60311 89108 464 51144 69333 465 31653 48550 466 55121 87873 467 36739 66142 468 20290 69352 469 86844 80544 470 90543 40885 471 36289 61112 472 42899 95984 473 19910 73884 474 16572 40307 475 22864 91559 476 68021 38491 477 49918 73786 478 93754 91029 479 51211 96235 480 98091 95113 481 51208 26252 482 12671 40285 483 61367 89030 484 58498 75949 485 26520 61255 486 16399 35061 487 26388 40307 488 20061 45050 489 42577 59248 490 46182 23803 491 45833 22608 492 75415 35192 493 45131 27513 494 78087 72412 495 37845 59937 496 73178 40307 497 38346 10790 498 36144 48550 499 95728 35192 500 24529 74785 501 13457 62690 502 80521 90830 503 26709 87903 504 96061 58362 505 39901 75949 506 59024 36414 507 70572 73484 508 26182 48550 509 54289 44962 510 77243 41357 511 45652 63563 512 61275 33760 513 76258 58116 514 87903 75949 515 36803 72708 516 34689 49298 517 78499 69964 518 97542 16399 519 99456 23803 520 31246 97810 521 67707 66916 522 53353 76845 523 72413 81639 524 77355 91427 525 11696 37641 526 38619 66916 527 58279 27513 528 32455 46733 529 13767 10790 530 53600 12534 531 52611 86767 532 69581 58116 533 84766 44962 534 25762 84153 535 75405 27675 536 94680 98620 537 19072 83025 538 64541 25303 539 47436 48379 540 55099 77486 541 62938 40285 542 85782 22822 543 49496 68211 544 26405 18321 545 33543 53744 546 98210 17305 547 26641 70987 548 78605 23803 549 48550 91029 550 91470 59527 551 76437 48391 552 26589 68552 553 37984 42659 554 47771 75949 555 69492 69964 556 30910 17034 557 72127 48550 558 20323 74549 559 68586 54811 560 85656 49347 561 50811 29122 562 91633 13067 563 97829 94888 564 64580 30618 565 87031 50862 566 16689 35192 567 93352 21275 568 91740 27513 569 86775 66916 570 63447 40735 571 69321 85095 572 21196 96099 573 40135 24597 574 94728 83025 575 68263 78089 576 49758 75949 577 58570 40307 578 70556 80983 579 28954 87903 580 23512 75949 581 79621 26912 582 23768 89108 583 68025 71387 584 94717 39913 585 32934 38491 586 25309 46226 587 31117 91819 588 28718 37008 589 11096 80983 590 82842 17899 591 10104 44147 592 15432 18566 593 58103 81227 594 36711 10790 595 62998 76676 596 56830 73884 597 74532 40285 598 10346 78375 599 43025 31492 600 31908 30023 601 38840 96892 602 42859 83025 603 16034 68263 604 56548 32521 605 36514 95622 606 93380 85880 607 89108 49638 608 14520 55668 609 61195 65113 610 59069 91029 611 75276 89108 612 94795 53666 613 16658 43105 614 23381 19836 615 80772 80983 616 22003 80790 617 78628 73884 618 53837 34325 619 53845 85258 620 87259 55484 621 96036 28264 622 43607 75949 623 90261 55158 624 97376 52565 625 11241 46873 626 13946 56491 627 48838 35216 628 26427 88573 629 24683 38491 630 61135 72412 631 39381 47195 632 66763 71602 633 50727 16399 634 26719 73008 635 91561 57060 636 27810 23803 637 25003 80469 638 87375 40479 639 47591 80117 640 15769 78617 641 62428 95360 642 58030 40285 643 42184 59248 644 16058 18264 645 49021 66916 646 60036 16399 647 79735 64973 648 28417 87903 649 75666 34050 650 45303 45905 651 99666 58844 652 83328 47904 653 34405 27513 654 40795 27513 655 94482 57076 656 73638 76842 657 11760 72412 658 18055 73884 659 42382 73884 660 74101 89766 661 53388 22330 662 80963 61832 663 35307 75326 664 24016 61479 665 76700 69002 666 11790 54811 667 37543 40735 668 23488 38262 669 79409 73517 670 84795 48550 671 72611 72142 672 24699 49298 673 43748 48550 674 89525 98314 675 67690 26597 676 77431 66916 677 18256 65012 678 47688 69964 679 27275 54811 680 28105 75949 681 99231 47666 682 10732 40307 683 96670 82188 684 67501 16141 685 24786 95724 686 72693 58116 687 11436 11225 688 44962 16427 689 11976 57220 690 23830 75949 691 20155 29692 692 49298 40758 693 15879 38491 694 46430 19053 695 58886 32623 696 38384 73884 697 54723 67754 698 40400 45721 699 11657 16399 700 45050 45050 701 85338 35986 702 83322 66916 703 47722 83411 704 16468 24658 705 95873 81506 706 41360 47035 707 66342 36775 708 87812 87399 709 28383 39066 710 91602 15602 711 40405 89236 712 77890 81548 713 98616 49298 714 22404 35192 715 54032 44962 716 52902 16399 717 91840 98314 718 63905 12686 719 10098 54811 720 11009 35192 721 88737 23803 722 64422 88518 723 37474 95536 724 41788 91339 725 76027 15249 726 17826 50042 727 79264 64640 728 98770 36874 729 13862 57804 730 38691 27513 731 21357 78686 732 32360 52496 733 18251 48550 734 38720 31160 735 36065 75949 736 35917 16399 737 60979 18939 738 91586 89952 739 28849 67949 740 40735 58746 741 26437 19975 742 86360 45050 743 35949 19228 744 83277 50098 745 38624 10790 746 52011 49393 747 39123 39337 748 27513 89108 749 62673 15222 750 94379 83025 751 23909 90571 752 77737 93244 753 70404 70858 754 62370 84696 755 84827 44218 756 53387 35250 757 87556 89108 758 80571 51193 759 26409 91029 760 13990 83025 761 11278 34702 762 16299 89667 763 63994 65610 764 86493 54811 765 29416 78479 766 17711 28383 767 80358 80983 768 56072 39436 769 93254 73884 770 91931 16399 771 53072 98128 772 24215 98633 773 90482 97373 774 21665 40735 775 64002 80983 776 84470 27470 777 81717 67708 778 41573 22587 779 46883 16167 780 19788 93408 781 41097 23282 782 80709 38138 783 37670 69964 784 49520 40544 785 19523 42044 786 83480 22439 787 67124 88126 788 90934 21464 789 87043 65017 790 50073 10790 791 81378 61975 792 51195 80983 793 87524 10790 794 54555 49298 795 49730 84396 796 91852 72412 797 14863 93792 798 74431 25266 799 39883 80983 800 99545 50098 801 49954 39659 802 50720 54616 803 82282 66849 804 27672 34776 805 48615 88195 806 16323 23803 807 34687 30556 808 84144 25955 809 43893 16399 810 58000 17912 811 63630 93219 812 42225 59248 813 10697 50098 814 84790 49298 815 84555 50098 816 11332 67228 817 55152 91029 818 17760 35192 819 74448 78826 820 72412 99596 821 81795 65194 822 28000 23577 823 58978 75949 824 97634 91029 825 12089 74439 826 21668 11140 827 98314 59248 828 27619 92514 829 34387 40285 830 64406 70596 831 54811 36254 832 28351 92362 833 79006 46580 834 49237 10460 835 30856 46374 836 59999 48734 837 76251 98298 838 14006 91029 839 88588 33976 840 97866 91029 841 11813 10790 842 91016 83025 843 43424 32540 844 83490 72412 845 78507 89604 846 91517 91029 847 55040 21407 848 21483 83837 849 47039 75811 850 97168 38491 851 96466 28383 852 66156 85652 853 50285 91029 854 14057 19440 855 73017 79572 856 33025 15856 857 97174 15804 858 65673 59248 859 19216 34215 860 44883 87903 861 30254 40285 862 31552 29668 863 76764 16427 864 60507 41588 865 18078 39147 866 46186 54811 867 90898 23803 868 23982 40735 869 37504 80710 870 72585 89108 871 17791 84089 872 79779 66916 873 25517 57516 874 54064 54811 875 47343 59248 876 11730 16399 877 14957 23803 878 30186 14989 879 66079 89338 880 82720 66916 881 59760 44962 882 23159 77329 883 21390 50098 884 12330 90747 885 38607 53663 886 96534 97111 887 65278 58227 888 48760 91626 889 34518 47541 890 79376 48439 891 40307 36080 892 59634 68532 893 16764 51086 894 20484 10950 895 40175 72383 896 12457 70481 897 56023 34025 898 63916 58517 899 46289 70209 900 91143 44935 901 65424 70887 902 39578 52243 903 79985 22203 904 72984 35192 905 41823 76917 906 98393 10103 907 48951 40735 908 51888 89069 909 85621 44767 910 49048 27513 911 48878 87903 912 91067 73884 913 67152 73125 914 80589 59248 915 80824 52481 916 65118 59248 917 66648 83025 918 17766 13909 919 83672 35572 920 81351 42040 921 72780 87903 922 87114 75949 923 74871 29739 924 62623 73816 925 68716 49219 926 72795 72092 927 97700 40307 928 80913 80983 929 21100 37233 930 49723 10790 931 30881 80895 932 42287 28982 933 90849 50862 934 13053 14799 935 90689 50862 936 91029 19117 937 61953 43248 938 67212 50164 939 70587 31660 940 50801 40285 941 44701 68049 942 67526 72412 943 64537 98405 944 10820 23823 945 94953 57422 946 93517 72412 947 84240 45050 948 72049 80983 949 17021 10790 950 41393 72559 951 88520 57245 952 63317 28383 953 28723 74185 954 64942 27513 955 10994 34190 956 57068 93681 957 15289 53584 958 20900 35192 959 32744 41588 960 18435 72823 961 95710 35192 962 14710 69585 963 31598 87903 964 63543 10790 965 29870 91029 966 20129 16427 967 21868 49298 968 76460 73884 969 65538 72412 970 84172 51085 971 77952 35689 972 26417 78889 973 93014 89108 974 66327 13137 975 40867 10790 976 65286 76246 977 93712 91171 978 73589 30084 979 91733 49842 980 55558 37212 981 11506 83025 982 59048 71853 983 62575 73247 984 96799 92730 985 46068 93958 986 32722 12454 987 42557 26234 988 83134 54811 989 52665 73128 990 38085 69964 991 33365 22988 992 74033 87903 993 49743 38491 994 47311 92414 995 41588 38093 996 78063 48550 997 83201 80983 998 57980 35192 999 58451 71130 1000 81627 56209