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