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