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