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