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