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