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