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