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