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