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