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