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