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