1000
516 329 324 945 486 293 706 57 845 86 133 525 896 46 75 51 135 739 220 842 117 158 417 697 215 420 403 285 38 816 716 243 627 637 458 845 935 305 555 452 692 368 607 582 32 167 397 774 769 135 126 96 976 37 535 870 288 835 620 694 895 191 788 449 158 358 497 160 384 822 971 707 703 639 721 45 790 459 296 968 973 211 695 167 482 312 847 373 420 220 878 365 128 98 132 79 996 181 848 682 621 912 98 502 248 271 916 978 671 299 21 652 662 347 925 619 263 397 430 107 276 669 691 678 629 109 14 511 138 900 807 617 777 746 147 546 243 267 0 702 232 887 130 865 125 435 263 971 381 22 277 480 237 861 27 570 801 582 916 924 431 662 664 187 156 696 372 730 394 392 590 201 514 654 345 834 458 489 70 3 134 461 504 599 354 504 897 420 677 844 506 318 648 421 521 339 236 776 130 924 124 78 711 144 17 456 726 645 520 495 486 209 752 802 870 485 217 129 676 754 759 216 519 166 62 353 751 683 17 46 614 773 735 374 394 693 471 197 234 163 18 629 186 40 671 830 881 321 59 217 26 312 835 554 601 61 652 235 846 966 839 482 90 124 0 517 726 895 335 39 58 370 417 575 323 967 331 248 148 808 182 75 347 856 14 154 525 17 797 843 9 444 358 17 117 938 280 150 590 632 617 223 314 918 910 252 628 591 336 651 31 628 682 46 509 472 765 467 478 618 930 144 844 192 742 303 11 590 887 146 305 903 864 971 403 912 896 315 655 509 997 504 809 665 501 942 793 750 151 400 614 765 215 405 809 448 305 336 553 219 210 946 541 156 990 445 331 995 115 357 82 167 6 956 298 206 507 524 695 711 302 748 481 141 667 778 90 824 824 166 87 97 64 950 589 982 321 967 970 469 348 291 954 876 496 623 519 921 953 858 410 976 985 408 168 108 831 430 262 634 643 262 651 460 696 425 818 529 441 629 10 413 77 50 845 624 889 315 341 798 20 510 711 576 818 9 428 222 899 276 421 342 587 1000 148 813 774 916 350 216 449 781 729 71 27 664 358 545 27 478 130 795 224 74 194 774 174 386 576 911 492 5 501 990 843 193 786 579 926 920 876 251 395 338 661 883 666 70 545 375 397 821 990 832 962 528 38 567 877 205 524 352 759 958 310 988 900 240 445 348 166 326 479 15 166 3 521 941 178 769 32 904 848 849 737 474 793 780 336 489 577 340 999 20 722 456 726 480 457 973 964 73 959 316 590 396 869 675 341 298 257 799 6 245 669 485 397 320 916 234 731 38 252 462 92 393 364 392 670 975 607 440 787 632 850 823 45 53 95 494 138 811 288 458 973 981 823 574 909 3 89 455 280 48 22 953 399 229 452 504 605 818 944 451 996 883 804 212 20 959 944 867 468 700 781 584 713 141 458 788 91 930 190 306 519 69 16 992 555 280 152 486 467 720 416 184 914 265 180 241 34 285 167 94 890 320 259 203 801 917 399 270 263 76 675 385 819 976 760 841 807 960 684 229 185 940 263 764 118 836 113 654 920 482 551 550 392 9 822 475 914 10 104 631 892 765 699 127 897 376 508 778 622 811 251 439 68 120 607 241 332 382 754 855 846 239 43 581 872 250 791 351 210 478 778 576 28 730 569 760 554 569 898 563 930 657 985 341 597 828 472 474 134 222 887 399 993 589 223 671 729 249 977 723 834 17 702 508 705 337 554 915 873 792 703 661 390 926 935 974 841 301 618 210 889 127 686 112 499 180 759 909 374 717 815 396 500 139 340 458 526 284 878 944 166 791 436 138 133 222 700 966 612 975 547 444 835 569 31 629 275 33 472 741 656 298 719 908 203 69 810 497 868 457 880 620 169 790 326 402 433 686 162 646 575 654 417 947 844 9 409 576 78 298 851 121 374 265 743 987 961 251 125 798 319 472 938 149 406 739 442 125 870 376 901 853 579 199 280 275 855 404 732 392 990 109 783 659 593 489 664 697 912 626 788 474 315 786 745 590 150 666 392 111 123 701 141 706 369 760 265 831 693 714 95 797 959 164 464 748 534 626 787 160 253 697 727 8 899 786 799 536 86 72 79 618 994 266 611 506 943 273 524 496 538 272 535 153 272 932 320 795 406 976 438 237 109 914 79 47 106 457 154 452 934 339 11 77 741 769 50 390 253 126 543 506 812 883 619 953 674 545 849 325 978 208 981 860 536 663 19 612 249 344 775 327 629 663 538 307 693 560 148 640 941 811 26 330 386 759