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