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