1 0 0 3 1 1 2 2 2 6 3 3 7 4 4 5 5 5 8 6 6 9 7 7 11 8 8 14 9 9 15 10 10 13 11 11 16 12 12 17 13 13 19 14 14 20 15 15 22 16 16 23 17 17 24 18 18 25 19 19 27 20 20 30 21 21 31 22 22 29 23 23 32 24 24 33 25 25 35 26 26 38 27 27 39 28 28 37 29 29 40 30 30 41 31 31 43 32 32 44 33 33 46 34 34 47 35 35 48 36 36 49 37 37 51 38 38 54 39 39 55 40 40 53 41 41 56 42 42 57 43 43 59 44 44 60 45 45 62 46 46 63 47 47 65 48 48 67 49 49 66 50 50 70 51 51 71 52 52 69 53 53 73 54 54 75 55 55 74 56 56 78 57 57 79 58 58 77 59 59 81 60 60 83 61 61 82 62 62 86 63 63 87 64 64 85 65 65 88 66 66 89 67 67 91 68 68 94 69 69 95 70 70 93 71 71 97 72 72 99 73 73 98 74 74 102 75 75 103 76 76 101 77 77 105 78 78 107 79 79 106 80 80 110 81 81 111 82 82 109 83 83 112 84 84 113 85 85 115 86 86 118 87 87 119 88 88 117 89 89 121 90 90 123 91 91 122 92 92 126 93 93 127 94 94 125 95 95 129 96 96 131 97 97 130 98 98 134 99 99 135 100 100 133 101 101 136 102 102 137 103 103 139 104 104 142 105 105 143 106 106 141 107 107 145 108 108 147 109 109 146 110 110 150 111 111 151 112 112 149 113 113 153 114 114 155 115 115 154 116 116 158 117 117 159 118 118 157 119 119 160 120 120 161 121 121 163 122 122 164 123 123 166 124 124 167 125 125 168 126 126 169 127 127 171 128 128 172 129 129 174 130 130 175 131 131 177 132 132 179 133 133 178 134 134 180 135 135 182 136 136 183 137 137 185 138 138 187 139 139 186 140 140 188 141 141 190 142 142 191 143 143 193 144 144 195 145 145 194 146 146 198 147 147 199 148 148 197 149 149 201 150 150 203 151 151 202 152 152 206 153 153 207 154 154 205 155 155 209 156 156 211 157 157 210 158 158 214 159 159 215 160 160 213 161 161 217 162 162 219 163 163 218 164 164 222 165 165 223 166 166 221 167 167 224 168 168 225 169 169 227 170 170 230 171 171 231 172 172 229 173 173 233 174 174 235 175 175 234 176 176 238 177 177 239 178 178 237 179 179 240 180 180 241 181 181 243 182 182 244 183 183 246 184 184 247 185 185 249 186 186 251 187 187 250 188 188 252 189 189 254 190 190 255 191 191 257 192 192 259 193 193 258 194 194 262 195 195 263 196 196 261 197 197 265 198 198 267 199 199 266 200 200 270 201 201 271 202 202 269 203 203 272 204 204 273 205 205 275 206 206 276 207 207 278 208 208 279 209 209 281 210 210 283 211 211 282 212 212 286 213 213 287 214 214 285 215 215 288 216 216 289 217 217 291 218 218 292 219 219 294 220 220 295 221 221 296 222 222 297 223 223 299 224 224 300 225 225 302 226 226 303 227 227 304 228 228 305 229 229 307 230 230 308 231 231 310 232 232 311 233 233 312 234 234 313 235 235 315 236 236 316 237 237 318 238 238 319 239 239 321 240 240 323 241 241 322 242 242 326 243 243 327 244 244 325 245 245 329 246 246 331 247 247 330 248 248 334 249 249 335 250 250 333 251 251 337 252 252 339 253 253 338 254 254 340 255 255 342 256 256 343 257 257 345 258 258 347 259 259 346 260 260 350 261 261 351 262 262 349 263 263 352 264 264 353 265 265 355 266 266 356 267 267 358 268 268 359 269 269 360 270 270 361 271 271 363 272 272 366 273 273 367 274 274 365 275 275 368 276 276 369 277 277 371 278 278 372 279 279 374 280 280 375 281 281 376 282 282 377 283 283 379 284 284 380 285 285 382 286 286 383 287 287 385 288 288 387 289 289 386 290 290 390 291 291 391 292 292 389 293 293 393 294 294 395 295 295 394 296 296 398 297 297 399 298 298 397 299 299 401 300 300 403 301 301 402 302 302 406 303 303 407 304 304 405 305 305 409 306 306 411 307 307 410 308 308 412 309 309 414 310 310 415 311 311 416 312 312 417 313 313 419 314 314 420 315 315 422 316 316 423 317 317 424 318 318 425 319 319 427 320 320 428 321 321 430 322 322 431 323 323 432 324 324 433 325 325 435 326 326 436 327 327 438 328 328 439 329 329 440 330 330 441 331 331 443 332 332 444 333 333 446 334 334 447 335 335 449 336 336 451 337 337 450 338 338 452 339 339 454 340 340 455 341 341 457 342 342 459 343 343 458 344 344 462 345 345 463 346 346 461 347 347 465 348 348 467 349 349 466 350 350 470 351 351 471 352 352 469 353 353 473 354 354 475 355 355 474 356 356 478 357 357 479 358 358 477 359 359 480 360 360 481 361 361 483 362 362 484 363 363 486 364 364 487 365 365 488 366 366 489 367 367 491 368 368 492 369 369 494 370 370 495 371 371 496 372 372 497 373 373 499 374 374 500 375 375 502 376 376 503 377 377 504 378 378 505 379 379 507 380 380 508 381 381 510 382 382 511 383 383 513 384 384 515 385 385 514 386 386 518 387 387 519 388 388 517 389 389 521 390 390 523 391 391 522 392 392 526 393 393 527 394 394 525 395 395 529 396 396 531 397 397 530 398 398 532 399 399 534 400 400 535 401 401 536 402 402 537 403 403 539 404 404 542 405 405 543 406 406 541 407 407 544 408 408 545 409 409 547 410 410 548 411 411 550 412 412 551 413 413 552 414 414 553 415 415 555 416 416 556 417 417 558 418 418 559 419 419 561 420 420 563 421 421 562 422 422 564 423 423 566 424 424 567 425 425 568 426 426 569 427 427 571 428 428 572 429 429 574 430 430 575 431 431 577 432 432 579 433 433 578 434 434 582 435 435 583 436 436 581 437 437 584 438 438 585 439 439 587 440 440 588 441 441 590 442 442 591 443 443 593 444 444 595 445 445 594 446 446 598 447 447 599 448 448 597 449 449 601 450 450 603 451 451 602 452 452 606 453 453 607 454 454 605 455 455 608 456 456 609 457 457 611 458 458 612 459 459 614 460 460 615 461 461 617 462 462 619 463 463 618 464 464 622 465 465 623 466 466 621 467 467 625 468 468 627 469 469 626 470 470 630 471 471 631 472 472 629 473 473 633 474 474 635 475 475 634 476 476 638 477 477 639 478 478 637 479 479 640 480 480 641 481 481 643 482 482 644 483 483 646 484 484 647 485 485 648 486 486 649 487 487 651 488 488 652 489 489 654 490 490 655 491 491 657 492 492 659 493 493 658 494 494 662 495 495 663 496 496 661 497 497 664 498 498 665 499 499 667 500 500 668 501 501 670 502 502 671 503 503 673 504 504 675 505 505 674 506 506 678 507 507 679 508 508 677 509 509 681 510 510 683 511 511 682 512 512 686 513 513 687 514 514 685 515 515 689 516 516 691 517 517 690 518 518 694 519 519 695 520 520 693 521 521 697 522 522 699 523 523 698 524 524 702 525 525 703 526 526 701 527 527 705 528 528 707 529 529 706 530 530 710 531 531 711 532 532 709 533 533 713 534 534 715 535 535 714 536 536 718 537 537 719 538 538 717 539 539 721 540 540 723 541 541 722 542 542 726 543 543 727 544 544 725 545 545 729 546 546 731 547 547 730 548 548 734 549 549 735 550 550 733 551 551 736 552 552 737 553 553 739 554 554 740 555 555 742 556 556 743 557 557 744 558 558 745 559 559 747 560 560 748 561 561 750 562 562 751 563 563 753 564 564 755 565 565 754 566 566 758 567 567 759 568 568 757 569 569 760 570 570 761 571 571 763 572 572 764 573 573 766 574 574 767 575 575 769 576 576 771 577 577 770 578 578 774 579 579 775 580 580 773 581 581 777 582 582 779 583 583 778 584 584 782 585 585 783 586 586 781 587 587 784 588 588 785 589 589 787 590 590 788 591 591 790 592 592 791 593 593 793 594 594 795 595 595 794 596 596 798 597 597 799 598 598 797 599 599 800 600 600 801 601 601 803 602 602 804 603 603 806 604 604 807 605 605 808 606 606 809 607 607 811 608 608 814 609 609 815 610 610 813 611 611 817 612 612 819 613 613 818 614 614 822 615 615 823 616 616 821 617 617 824 618 618 825 619 619 827 620 620 828 621 621 830 622 622 831 623 623 832 624 624 833 625 625 835 626 626 838 627 627 839 628 628 837 629 629 840 630 630 841 631 631 843 632 632 844 633 633 846 634 634 847 635 635 849 636 636 851 637 637 850 638 638 854 639 639 855 640 640 853 641 641 856 642 642 857 643 643 859 644 644 860 645 645 862 646 646 863 647 647 865 648 648 867 649 649 866 650 650 868 651 651 870 652 652 871 653 653 872 654 654 873 655 655 875 656 656 878 657 657 879 658 658 877 659 659 881 660 660 883 661 661 882 662 662 886 663 663 887 664 664 885 665 665 889 666 666 891 667 667 890 668 668 894 669 669 895 670 670 893 671 671 896 672 672 897 673 673 899 674 674 900 675 675 902 676 676 903 677 677 904 678 678 905 679 679 907 680 680 908 681 681 910 682 682 911 683 683 913 684 684 915 685 685 914 686 686 916 687 687 918 688 688 919 689 689 920 690 690 921 691 691 923 692 692 924 693 693 926 694 694 927 695 695 929 696 696 931 697 697 930 698 698 934 699 699 935 700 700 933 701 701 936 702 702 937 703 703 939 704 704 940 705 705 942 706 706 943 707 707 0 708 708 1 709 709 2 710 710 4 711 711 6 712 712 5 713 713 10 714 714 8 715 715 11 716 716 12 717 717 14 718 718 13 719 719 18 720 720 16 721 721 19 722 722 21 723 723 20 724 724 23 725 725 26 726 726 24 727 727 27 728 728 28 729 729 30 730 730 29 731 731 34 732 732 32 733 733 35 734 734 36 735 735 38 736 736 37 737 737 42 738 738 40 739 739 43 740 740 45 741 741 44 742 742 47 743 743 50 744 744 48 745 745 51 746 746 52 747 747 54 748 748 53 749 749 58 750 750 56 751 751 59 752 752 61 753 753 60 754 754 63 755 755 64 756 756 65 757 757 66 758 758 68 759 759 70 760 760 69 761 761 72 762 762 73 763 763 74 764 764 76 765 765 78 766 766 77 767 767 80 768 768 81 769 769 82 770 770 84 771 771 86 772 772 85 773 773 90 774 774 88 775 775 91 776 776 92 777 777 94 778 778 93 779 779 96 780 780 97 781 781 98 782 782 100 783 783 102 784 784 101 785 785 104 786 786 105 787 787 106 788 788 108 789 789 110 790 790 109 791 791 114 792 792 112 793 793 115 794 794 116 795 795 118 796 796 117 797 797 120 798 798 121 799 799 122 800 800 124 801 801 126 802 802 125 803 803 128 804 804 129 805 805 130 806 806 132 807 807 134 808 808 133 809 809 138 810 810 136 811 811 139 812 812 140 813 813 142 814 814 141 815 815 144 816 816 145 817 817 146 818 818 148 819 819 150 820 820 149 821 821 152 822 822 153 823 823 154 824 824 156 825 825 158 826 826 157 827 827 162 828 828 160 829 829 163 830 830 165 831 831 164 832 832 167 833 833 170 834 834 168 835 835 171 836 836 173 837 837 172 838 838 175 839 839 176 840 840 177 841 841 178 842 842 181 843 843 180 844 844 183 845 845 184 846 846 185 847 847 186 848 848 189 849 849 188 850 850 191 851 851 192 852 852 193 853 853 194 854 854 196 855 855 198 856 856 197 857 857 200 858 858 201 859 859 202 860 860 204 861 861 206 862 862 205 863 863 208 864 864 209 865 865 210 866 866 212 867 867 214 868 868 213 869 869 216 870 870 217 871 871 218 872 872 220 873 873 222 874 874 221 875 875 226 876 876 224 877 877 227 878 878 228 879 879 230 880 880 229 881 881 232 882 882 233 883 883 234 884 884 236 885 885 238 886 886 237 887 887 242 888 888 240 889 889 243 890 890 245 891 891 244 892 892 247 893 893 248 894 894 249 895 895 250 896 896 253 897 897 252 898 898 255 899 899 256 900 900 257 901 901 258 902 902 260 903 903 262 904 904 261 905 905 264 906 906 265 907 907 266 908 908 268 909 909 270 910 910 269 911 911 274 912 912 272 913 913 275 914 914 277 915 915 276 916 916 279 917 917 280 918 918 281 919 919 282 920 920 284 921 921 286 922 922 285 923 923 290 924 924 288 925 925 291 926 926 293 927 927 292 928 928 295 929 929 298 930 930 296 931 931 299 932 932 301 933 933 300 934 934 303 935 935 306 936 936 304 937 937 307 938 938 309 939 939 308 940 940 311 941 941 314 942 942 312 943 943 315 944 944 317 945 945 316 946 946 319 947 947 320 948 948 321 949 949 322 950 950 324 951 951 326 952 952 325 953 953 328 954 954 329 955 955 330 956 956 332 957 957 334 958 958 333 959 959 336 960 960 337 961 961 338 962 962 341 963 963 340 964 964 343 965 965 344 966 966 345 967 967 346 968 968 348 969 969 350 970 970 349 971 971 354 972 972 352 973 973 355 974 974 357 975 975 356 976 976 359 977 977 362 978 978 360 979 979 363 980 980 364 981 981 366 982 982 365 983 983 370 984 984 368 985 985 371 986 986 373 987 987 372 988 988 375 989 989 378 990 990 376 991 991 379 992 992 381 993 993 380 994 994 383 995 995 384 996 996 385 997 997 386 998 998 388 999 999 390 1000 1000 389 1001 1001 392 1002 1002 393 1003 1003 394 1004 1004 396 1005 1005 398 1006 1006 397 1007 1007 400 1008 1008 401 1009 1009 402 1010 1010 404 1011 1011 406 1012 1012 405 1013 1013 408 1014 1014 409 1015 1015 410 1016 1016 413 1017 1017 412 1018 1018 415 1019 1019 418 1020 1020 416 1021 1021 419 1022 1022 421 1023 1023 420 1024 1024 423 1025 1025 426 1026 1026 424 1027 1027 427 1028 1028 429 1029 1029 428 1030 1030 431 1031 1031 434 1032 1032 432 1033 1033 435 1034 1034 437 1035 1035 436 1036 1036 439 1037 1037 442 1038 1038 440 1039 1039 443 1040 1040 445 1041 1041 444 1042 1042 447 1043 1043 448 1044 1044 449 1045 1045 450 1046 1046 453 1047 1047 452 1048 1048 455 1049 1049 456 1050 1050 457 1051 1051 458 1052 1052 460 1053 1053 462 1054 1054 461 1055 1055 464 1056 1056 465 1057 1057 466 1058 1058 468 1059 1059 470 1060 1060 469 1061 1061 472 1062 1062 473 1063 1063 474 1064 1064 476 1065 1065 478 1066 1066 477 1067 1067 482 1068 1068 480 1069 1069 483 1070 1070 485 1071 1071 484 1072 1072 487 1073 1073 490 1074 1074 488 1075 1075 491 1076 1076 493 1077 1077 492 1078 1078 495 1079 1079 498 1080 1080 496 1081 1081 499 1082 1082 501 1083 1083 500 1084 1084 503 1085 1085 506 1086 1086 504 1087 1087 507 1088 1088 509 1089 1089 508 1090 1090 511 1091 1091 512 1092 1092 513 1093 1093 514 1094 1094 516 1095 1095 518 1096 1096 517 1097 1097 520 1098 1098 521 1099 1099 522 1100 1100 524 1101 1101 526 1102 1102 525 1103 1103 528 1104 1104 529 1105 1105 530 1106 1106 533 1107 1107 532 1108 1108 535 1109 1109 538 1110 1110 536 1111 1111 539 1112 1112 540 1113 1113 542 1114 1114 541 1115 1115 546 1116 1116 544 1117 1117 547 1118 1118 549 1119 1119 548 1120 1120 551 1121 1121 554 1122 1122 552 1123 1123 555 1124 1124 557 1125 1125 556 1126 1126 559 1127 1127 560 1128 1128 561 1129 1129 562 1130 1130 565 1131 1131 564 1132 1132 567 1133 1133 570 1134 1134 568 1135 1135 571 1136 1136 573 1137 1137 572 1138 1138 575 1139 1139 576 1140 1140 577 1141 1141 578 1142 1142 580 1143 1143 582 1144 1144 581 1145 1145 586 1146 1146 584 1147 1147 587 1148 1148 589 1149 1149 588 1150 1150 591 1151 1151 592 1152 1152 593 1153 1153 594 1154 1154 596 1155 1155 598 1156 1156 597 1157 1157 600 1158 1158 601 1159 1159 602 1160 1160 604 1161 1161 606 1162 1162 605 1163 1163 610 1164 1164 608 1165 1165 611 1166 1166 613 1167 1167 612 1168 1168 615 1169 1169 616 1170 1170 617 1171 1171 618 1172 1172 620 1173 1173 622 1174 1174 621 1175 1175 624 1176 1176 625 1177 1177 626 1178 1178 628 1179 1179 630 1180 1180 629 1181 1181 632 1182 1182 633 1183 1183 634 1184 1184 636 1185 1185 638 1186 1186 637 1187 1187 642 1188 1188 640 1189 1189 643 1190 1190 645 1191 1191 644 1192 1192 647 1193 1193 650 1194 1194 648 1195 1195 651 1196 1196 653 1197 1197 652 1198 1198 655 1199 1199 656 1200 1200 657 1201 1201 658 1202 1202 660 1203 1203 662 1204 1204 661 1205 1205 666 1206 1206 664 1207 1207 667 1208 1208 669 1209 1209 668 1210 1210 671 1211 1211 672 1212 1212 673 1213 1213 674 1214 1214 676 1215 1215 678 1216 1216 677 1217 1217 680 1218 1218 681 1219 1219 682 1220 1220 684 1221 1221 686 1222 1222 685 1223 1223 688 1224 1224 689 1225 1225 690 1226 1226 692 1227 1227 694 1228 1228 693 1229 1229 696 1230 1230 697 1231 1231 698 1232 1232 700 1233 1233 702 1234 1234 701 1235 1235 704 1236 1236 705 1237 1237 706 1238 1238 708 1239 1239 710 1240 1240 709 1241 1241 712 1242 1242 713 1243 1243 714 1244 1244 716 1245 1245 718 1246 1246 717 1247 1247 720 1248 1248 721 1249 1249 722 1250 1250 724 1251 1251 726 1252 1252 725 1253 1253 728 1254 1254 729 1255 1255 730 1256 1256 732 1257 1257 734 1258 1258 733 1259 1259 738 1260 1260 736 1261 1261 739 1262 1262 741 1263 1263 740 1264 1264 743 1265 1265 746 1266 1266 744 1267 1267 747 1268 1268 749 1269 1269 748 1270 1270 751 1271 1271 752 1272 1272 753 1273 1273 754 1274 1274 756 1275 1275 758 1276 1276 757 1277 1277 762 1278 1278 760 1279 1279 763 1280 1280 765 1281 1281 764 1282 1282 767 1283 1283 768 1284 1284 769 1285 1285 770 1286 1286 772 1287 1287 774 1288 1288 773 1289 1289 776 1290 1290 777 1291 1291 778 1292 1292 780 1293 1293 782 1294 1294 781 1295 1295 786 1296 1296 784 1297 1297 787 1298 1298 789 1299 1299 788 1300 1300 791 1301 1301 792 1302 1302 793 1303 1303 794 1304 1304 796 1305 1305 798 1306 1306 797 1307 1307 802 1308 1308 800 1309 1309 803 1310 1310 805 1311 1311 804 1312 1312 807 1313 1313 810 1314 1314 808 1315 1315 811 1316 1316 812 1317 1317 814 1318 1318 813 1319 1319 816 1320 1320 817 1321 1321 818 1322 1322 820 1323 1323 822 1324 1324 821 1325 1325 826 1326 1326 824 1327 1327 827 1328 1328 829 1329 1329 828 1330 1330 831 1331 1331 834 1332 1332 832 1333 1333 835 1334 1334 836 1335 1335 838 1336 1336 837 1337 1337 842 1338 1338 840 1339 1339 843 1340 1340 845 1341 1341 844 1342 1342 847 1343 1343 848 1344 1344 849 1345 1345 850 1346 1346 852 1347 1347 854 1348 1348 853 1349 1349 858 1350 1350 856 1351 1351 859 1352 1352 861 1353 1353 860 1354 1354 863 1355 1355 864 1356 1356 865 1357 1357 866 1358 1358 869 1359 1359 868 1360 1360 871 1361 1361 874 1362 1362 872 1363 1363 875 1364 1364 876 1365 1365 878 1366 1366 877 1367 1367 880 1368 1368 881 1369 1369 882 1370 1370 884 1371 1371 886 1372 1372 885 1373 1373 888 1374 1374 889 1375 1375 890 1376 1376 892 1377 1377 894 1378 1378 893 1379 1379 898 1380 1380 896 1381 1381 899 1382 1382 901 1383 1383 900 1384 1384 903 1385 1385 906 1386 1386 904 1387 1387 907 1388 1388 909 1389 1389 908 1390 1390 911 1391 1391 912 1392 1392 913 1393 1393 914 1394 1394 917 1395 1395 916 1396 1396 919 1397 1397 922 1398 1398 920 1399 1399 923 1400 1400 925 1401 1401 924 1402 1402 927 1403 1403 928 1404 1404 929 1405 1405 930 1406 1406 932 1407 1407 934 1408 1408 933 1409 1409 938 1410 1410 936 1411 1411 939 1412 1412 941 1413 1413 940 1414 1414 943 1415 1415