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