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