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