1000
282 858 10 431 93 451 831 768 325 46 246 968 895 43 423 34 923 474 667 139 11 32 74 230 482 795 289 245 380 817 922 553 526 542 38 865 424 291 679 849 525 141 799 76 932 43 128 208 266 609 466 631 939 478 361 451 70 152 993 545 476 249 681 585 960 98 621 152 852 326 365 441 818 93 600 610 440 504 682 291 388 276 87 813 163 142 833 986 720 243 576 30 663 260 564 431 565 184 326 509 642 657 43 92 950 447 982 890 460 950 325 440 694 243 953 799 602 23 282 955 326 107 850 236 568 587 362 388 817 818 168 495 228 266 361 683 423 264 751 466 509 371 823 485 988 19 737 847 371 724 561 298 346 547 137 388 702 372 999 589 946 460 346 224 511 212 797 720 676 852 98 932 843 547 596 861 358 49 194 291 604 640 159 126 921 918 450 282 26 757 849 162 27 289 705 249 11 464 817 95 986 118 634 752 868 733 358 656 999 708 704 572 932 596 126 678 518 985 135 98 487 11 599 274 342 640 466 262 200 18 135 924 307 126 768 697 725 358 114 563 157 376 781 266 447 849 644 376 948 88 661 704 993 414 23 118 618 790 898 751 358 86 242 572 580 84 573 764 200 667 114 936 150 728 128 957 610 510 899 561 361 565 561 98 282 526 202 365 878 561 946 524 965 141 325 342 667 560 758 235 858 827 893 787 435 779 924 580 322 580 193 292 729 285 948 752 542 358 708 701 208 618 870 820 46 434 142 623 426 364 388 10 31 247 504 88 513 915 815 657 372 272 346 365 758 724 211 703 908 208 98 545 587 509 377 756 731 43 525 871 641 226 340 953 604 600 937 10 393 908 745 624 504 935 109 88 948 849 224 971 88 150 271 532 235 464 388 346 358 138 743 956 815 677 807 267 88 945 331 891 870 34 661 15 426 372 250 453 162 211 435 641 679 612 485 26 511 195 230 609 159 429 760 505 455 276 518 66 641 242 776 843 589 572 307 980 216 725 818 450 485 208 451 612 853 657 158 263 442 245 193 551 791 325 585 526 239 671 922 665 383 288 35 196 932 482 806 466 371 762 228 935 837 865 804 498 978 301 779 298 171 545 948 246 139 31 899 814 742 15 920 274 692 644 66 301 495 897 88 478 491 274 982 247 528 955 982 596 804 235 485 743 885 953 282 325 754 230 721 568 304 812 848 677 340 168 102 142 756 890 737 291 285 853 813 650 432 646 440 769 126 923 897 871 960 556 657 321 371 781 200 431 675 312 285 568 282 970 226 102 447 887 991 316 142 27 895 908 576 296 259 524 87 847 86 725 897 970 798 224 38 565 372 953 738 187 513 812 240 561 451 898 305 43 733 569 644 377 177 776 526 524 511 757 56 890 986 216 513 321 511 18 460 589 183 564 203 187 720 986 393 76 758 398 595 996 997 149 596 88 168 682 997 558 405 118 937 171 522 974 242 47 259 35 187 99 74 142 249 733 158 887 640 321 172 107 675 391 20 95 380 939 819 629 586 177 280 764 709 242 253 178 648 885 534 558 851 482 266 836 312 495 416 128 305 999 524 950 853 518 580 769 932 528 573 250 98 13 36 918 580 126 142 393 23 194 666 513 545 697 128 441 939 540 987 629 383 706 624 948 137 849 388 551 405 44 342 729 276 434 28 770 296 642 814 139 286 733 682 709 695 491 388 787 128 485 657 917 44 838 364 453 569 236 758 191 158 105 158 696 178 702 139 84 525 539 948 851 47 70 539 915 15 534 504 150 731 919 176 451 814 243 172 936 758 893 667 158 151 715 984 818 663 955 126 67 696 553 891 703 20 202 230 31 288 895 266 987 560 263 337 753 202 177 228 312 463 538 505 971 18 870 362 109 175 509 836 358 801 723 202 823 476 799 935 427 958 787 259 706 292 790 409 9 372 774 19 211 553 737 303 540 131 958 635 150 885 984 509 996 230 791 889 491 890 26 617 508 107 262 184 377 586 754 291 409 137 723 89 908 745 202 333 150 224 149 455 597 68 453 189 893 226 967 985 665 18 176 291 302 107 249 36 987 405 435 922 271 534 474 25 23 662 509 820 416 850 771 596 617 88 129 861 243 999 984 183 230 398 823 967 718 457 183 126 252 588 563 114 472 137 131 217 646 725 304 935 991 967 662 720 337 476 538 599 968 203 99 599 224 203 441 831 677 326 441 11 827 278 523 282 342 641 715 947 504 669 380 169 500 240 924 585 429 759 322 999 442 377 228 431 249 88 441 405 54 504 980 272 278 -532 -634 -44 -70 -84 -576 -131 -25 -525 -150 -15 -820 -312 -760 -553 -44 -953 -676 -398 -756 -230 -587 -426 -518 -950 -599 -891 -184 -908 -657 -751 -102 -545 -288 -743 -463 -518 -849 -126 -88 -681 -440 -971 -451 -801 -733 -326 -325 -264 -831 -409 -451 -871 -301 -183 -725 -667 -451 -23 -32 -985 -457 -388 -246 -228 -721 -817 -36 -230 -377 -618 -10 -15 -305 -923 -371 -908 -358 -105 -474 -667 -342 -540 -948 -751 -899 -289 -545 -812 -523 -589 -545 -68 -30 -768 -126 -138 -663 -388 -431 -118 -865 -18 -560 -564 -474 -202 -296 -10 -236 -720 -250 -504 -980 -756 -814 -524 -948 -202 -278 -849 -511 -991 -128 -818 -524 -758 -19 -610 -596 -442 -967 -818 -114 -898 -848 -498 -340 -679 -23 -870 -667 -89 -18 -249 -525 -897 -216 -266 -391 -224 -671 -303 -245 -495 -580 -126 -325 -820 -631 -817 -128 -151 -580 -177 -525 -242 -226 -331 -84 -312 -588 -158 -642 -450 -725 -128 -504 -175 -945 -837 -212 -128 -661 -641 -836 -159 -675 -640 -15 -388 -26 -895 -326 -194 -650 -956 -936 -441 -572 -958 -56 -849 -852 -754 -586 -723 -565 -447 -393 -640 -641 -937 -316 -509 -596 -142 -38 -561 -999 -510 -291 -176 -553 -617 -217 -296 -948 -526 -970 -137 -528 -887 -87 -371 -679 -807 -986 -899 -806 -292 -718 -677 -126 -187 -171 -999 -245 -967 -285 -491 -13 -950 -28 -738 -142 -282 -178 -280 -640 -737 -93 -263 -769 -948 -46 -568 -150 -194 -107 -202 -743 -982 -377 -542 -697 -705 -243 -485 -560 -538 -253 -753 -43 -984 -102 -282 -485 -266 -758 -665 -868 -827 -683 -240 -843 -128 -19 -799 -609 -918 -450 -460 -129 -580 -986 -460 -724 -960 -589 -149 -871 -114 -86 -539 -274 -725 -731 -540 -288 -23 -953 -819 -88 -833 -447 -208 -932 -195 -524 -434 -211 -242 -242 -172 -447 -191 -511 -372 -361 -513 -852 -126 -322 -424 -511 -618 -230 -823 -135 -466 -599 -558 -947 -870 -551 -737 -817 -728 -587 -10 -267 -11 -380 -67 -47 -31 -937 -172 -423 -54 -302 -836 -272 -917 -321 -563 -239 -203 -558 -752 -464 -358 -565 -831 -996 -358 -955 -398 -769 -92 -235 -526 -36 -109 -427 -224 -326 -935 -358 -337 -551 -847 -657 -74 -891 -600 -667 -286 -27 -208 -509 -35 -393 -915 -202 -18 -970 -999 -932 -441 -513 -365 -798 -924 -762 -663 -35 -657 -509 -924 -26 -416 -88 -377 -897 -849 -580 -405 -919 -372 -890 -997 -203 -11 -742 -677 -278 -696 -150 -491 -745 -272 -757 -162 -282 -569 -657 -442 -187 -953 -142 -666 -729 -321 -98 -135 -200 -758 -380 -346 -580 -70 -453 -682 -602 -770 -88 -635 -887 -208 -31 -987 -624 -893 -596 -745 -853 -178 -915 -20 -573 -504 -93 -388 -189 -561 -431 -76 -843 -478 -95 -920 -518 -968 -827 -697 -986 -203 -158 -572 -226 -790 -641 -157 -513 -141 -953 -66 -388 -870 -893 -950 -88 -781 -804 -561 -504 -621 -526 -171 -126 -815 -669 -838 -644 -266 -142 -34 -226 -709 -228 -304 -464 -158 -451 -276 -723 -196 -274 -9 -466 -644 -522 -435 -98 -416 -968 -965 -791 -43 -169 -804 -485 -776 -922 -935 -200 -362 -982 -596 -141 -88 -629 -376 -346 -932 -291 -889 -799 -337 -797 -509 -263 -701 -453 -921 -158 -597 -504 -865 -585 -682 -675 -553 -460 -706 -936 -814 -733 -662 -11 -333 -247 -604 -34 -266 -987 -694 -246 -364 -642 -243 -539 -850 -325 -978 -656 -847 -547 -908 -86 -476 -163 -774 -405 -476 -764 -429 -993 -202 -187 -504 -168 -126 -585 -768 -383 -955 -505 -980 -485 -629 -224 -599 -159 -561 -431 -895 -648 -641 -142 -271 -487 -720 -851 -426 -720 -729 -731 -491 -307 -861 -482 -482 -715 -939 -704 -405 -813 -538 -346 -898 -432 -485 -260 -818 -66 -298 -152 -702 -993 -754 -249 -733 -509 -365 -958 -137 -565 -897 -704 -572 -924 -27 -815 -703 -372 -999 -435 -388 -999 -307 -26 -139 -853 -137 -971 -158 -779 -922 -211 -576 -974 -453 -472 -858 -152 -388 -759 -46 -230 -771 -43 -779 -362 -586 -568 -236 -589 -885 -371 -200 -291 -274 -482 -405 -677 -528 -376 -923 -511 -451 -939 -715 -259 -235 -758 -526 -781 -984 -890 -228 -946 -706 -193 -74 -441 -624 -150 -612 -812 -249 -604 -661 -708 -285 -325 -289 -441 -242 -682 -162 -561 -312 -249 -365 -183 -109 -11 -271 -88 -282 -996 -177 -986 -98 -340 -99 -878 -885 -991 -228 -322 -692 -346 -861 -114 -547 -224 -813 -282 -818 -47 -435 -266 -849 -922 -791 -107 -98 -252 -434 -342 -795 -409 -890 -513 -509 -596 -321 -563 -441 -429 -88 -646 -678 -695 -508 -948 -372 -960 -790 -984 -568 -935 -393 -342 -957 -708 -371 -644 -612 -249 -342 -139 -646 -38 -184 -142 -776 -709 -298 -259 -853 -325 -850 -662 -724 -358 -230 -703 -139 -377 -276 -118 -118 -478 -235 -948 -414 -150 -440 -107 -737 -720 -301 -505 -139 -569 -88 -534 -361 -168 -276 -291 -534 -890 -455 -364 -988 -31 -665 -823 -361 -372 -987 -967 -657 -752 -696 -383 -823 -466 -285 -177 -564 -985 -208 -764 -623 -495 -610 -939 -733 -814 -758 -935 -380 -358 -595 -466 -211 -23 -240 -216 -243 -262 -193 -262 -99 -787 -556 -545 -702 -259 -43 -725 -787 -230 -76 -305 -542 -895 -851 -282 -107 -885 -908 -757 -291 -20 -18 -455 -176 -224 -440 -168 -524 -585 -282 -858 -149 -500 -982 -573 -423 -43 -95 -183 -495 -476 -49 -247 -431 -243 -600 -358 -87 -932 -918 -98 -98 -955 -617 -609 -534 -291 -787 -131 -946 -799 -997 -137 -304 -893 -326 -250 -932 -292