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