===INPUT=== 1000 3310 3558 1810 3203 5996 8176 1199 5973 7778 8975 796 5452 7853 8453 3345 5486 2030 8186 2908 4804 2762 5070 700 8136 6150 9768 1161 6596 1779 7179 1049 2102 2273 8888 2288 7287 5541 6435 196 8529 2264 7573 5951 9440 1043 9825 4131 4140 1875 4753 6301 9549 759 5970 2987 3433 1581 9746 5564 6734 7640 9500 330 2243 3870 9401 1047 8111 3784 5266 1529 9142 4114 5788 479 9966 7417 9889 442 763 4407 8712 4213 9859 4478 5595 992 3605 4175 8348 2977 8372 2540 3976 5463 6897 5605 8711 86 9912 605 774 1436 2663 453 3246 4321 8481 2373 3900 655 2258 3829 4630 7974 8403 6618 8492 2217 2542 487 7886 1461 9836 707 1068 2907 7957 7262 7916 1535 4020 1371 3334 2293 4571 6253 7024 1726 2113 1849 9107 1769 1976 2484 5924 6511 8094 254 5828 1324 3742 954 6544 742 1158 6276 8320 1848 6892 2619 3877 7536 9587 779 6524 1228 5578 2145 7226 4094 8677 1475 2821 791 3248 2794 8458 4483 5025 1780 5209 5585 9150 867 2953 2550 6511 379 8809 3813 7282 4106 7333 4307 5067 3476 5422 7353 7788 837 4408 3994 8198 6923 7611 4950 8717 2418 7088 2541 8210 705 1957 6565 7648 1155 2632 3526 6841 3850 5668 2727 4752 4003 8932 3302 8127 6614 8975 3002 5156 862 9670 968 9866 1549 2587 8221 8727 177 3565 2197 6409 2298 8788 1787 4913 3007 9527 3661 7579 952 8362 714 3499 1319 5119 3644 9371 2650 3972 2181 9947 5893 6587 1723 1857 3002 9554 6294 8052 970 3330 1745 4974 1540 5071 3997 6473 598 968 653 2595 2510 7859 1224 3608 624 5471 34 7203 354 7258 4117 7047 7910 9561 2353 7406 6959 8659 3875 8594 1968 6539 874 2314 2730 9549 730 7510 418 655 4071 8336 3863 6532 1090 7926 2507 8212 377 5733 345 2520 1402 4119 264 316 117 882 3767 8531 1571 4196 1876 7109 633 3316 2044 2685 1858 8715 6462 7315 850 6188 349 3121 33 9789 6124 7852 2745 9513 3443 8538 6210 8158 952 3988 864 9752 526 1879 6234 9667 3761 6054 3124 3493 7604 8918 4411 5294 1108 9354 2591 7317 637 1726 3755 9926 537 8127 8954 9335 933 6154 487 4224 222 458 4715 6117 2714 2792 2177 7431 3193 8254 3285 8899 6573 7245 799 7689 412 5723 1281 8649 2210 5697 1144 4793 9271 9771 1972 8840 4881 5190 943 9834 2964 4725 2414 9297 2553 8376 4624 7913 2052 5427 2467 7016 6254 7977 3716 4964 1086 4478 1594 5029 8709 9217 411 2132 1097 5258 207 6211 3823 5991 567 1292 2447 8704 3108 9122 5931 9063 1856 2928 3264 9079 5467 9094 4786 8657 1413 4004 2193 6621 2721 8466 1104 1667 6738 9928 1308 9681 899 6945 1292 6431 2520 6415 1630 8842 1835 3976 910 8409 7527 8452 3172 9827 21 4053 1676 6913 22 2726 687 2253 6898 8533 2571 9984 3261 4982 2948 5228 1353 7080 6624 6647 2058 4299 491 5403 639 2010 3171 6571 5694 7279 3407 4457 1453 6602 2344 5294 3809 4286 1656 3102 4720 9818 559 6590 1629 3867 6123 8928 1703 3203 3830 5250 3786 8066 6478 7099 1831 9391 4910 8024 1502 7253 674 2742 3292 7691 892 9121 6623 8406 2518 6631 7239 8133 1289 7664 4550 6102 2049 2622 454 7975 2130 7550 8492 9104 2289 8223 4047 9963 4169 8393 2657 8734 374 2756 6135 6275 4144 9058 1557 6167 4399 5281 308 634 1574 8553 888 7796 2710 3748 1838 6175 4252 8499 323 513 6358 9861 578 2899 1850 1893 1131 5030 3601 4939 266 7767 80 4374 2129 5443 1498 9254 6853 8010 3042 9550 463 1947 390 5368 4079 7497 2643 4161 4298 6206 1722 7185 5344 7352 555 1877 126 1594 3298 3804 1120 6875 399 2073 392 645 28 3727 944 5952 8707 9321 3192 9294 1324 1886 4187 8994 1844 5500 262 8638 276 2874 2273 8610 5746 5825 206 1590 2319 7554 6067 6982 3297 3495 4299 9197 2508 4567 3022 5458 1379 9262 7001 8086 1537 7678 543 6959 243 9390 2022 9684 332 9115 5166 8231 167 6464 3896 6205 2066 2834 1602 8489 1584 7896 428 8809 442 6718 397 8498 3451 6486 5949 7208 3769 8468 1996 8895 1906 9559 3648 5401 858 1034 801 8173 2532 7546 2741 5446 299 9693 1290 5333 82 8435 3109 7278 2266 2415 836 5498 4073 7266 5797 8291 5061 7133 6810 9034 1496 8896 7778 8351 5631 7638 1639 3623 3848 8591 877 2875 1287 8660 727 1103 1444 4045 5671 7850 8959 9416 2651 5249 2143 7265 1879 9538 3947 7590 2150 7776 3726 9999 2912 6915 83 7111 341 5713 1170 4530 1966 4204 2201 5430 3616 7426 6863 7643 1593 7001 417 2479 1930 9375 3376 6784 1530 7757 8507 9500 4360 9101 5879 8193 821 5113 5303 6206 2749 5768 3567 3571 7198 9923 1833 3835 3999 8961 731 4872 1633 4531 4728 7310 842 9564 6550 7283 668 2855 661 2913 1286 7785 40 8225 109 2437 7687 8892 2569 7859 1656 2139 3590 4679 2709 5428 1156 8510 698 7248 3083 9851 4797 6251 2098 3104 5506 8763 2580 7976 6699 8801 411 5114 1452 4213 3352 4392 4143 8391 4122 9887 6465 8772 2816 6302 3951 5999 72 2079 1046 5577 4251 5808 2680 9488 2883 4491 979 5784 5831 9900 1366 2214 1375 4663 3114 7814 3319 4129 5208 6821 393 4470 447 7580 2479 2839 2548 7696 1278 6274 990 1028 5947 7815 4767 5396 1819 4622 271 1637 8164 9602 2694 6365 5795 5871 1385 8779 6249 7471 1358 8890 2125 7070 2251 9000 5711 5715 2449 3768 7778 8602 4836 4977 1863 2849 303 331 3965 4103 5918 8601 4886 6642 4458 9561 4664 7714 346 9974 1286 1788 2381 8682 1270 6394 7086 9439 1575 3804 7258 9270 6083 6440 1612 8297 4394 7031 1205 3897 2711 4118 4727 5517 2809 7981 5778 8986 6559 7726 1268 1294 5359 6198 2229 5255 1586 4408 4633 7824 1931 9328 883 4243 1833 2485 6469 8271 3831 7493 4681 8469 1894 8784 2249 6707 1101 3301 958 1935 5966 8142 1370 9215 1216 8450 112 5557 863 3502 5808 7145 2977 3543 644 7850 2427 2744 3242 6022 582 2929 2064 7595 7005 9474 1380 8907 1000 2963 4638 6825 4270 5975 2035 3044 4374 7970 1186 6959 1167 2392 5209 8161 7320 7441 4049 6052 1002 1939 1161 9811 3199 3429 8899 9297 5154 9316 7590 8805 2553 3592 7713 9415 2056 9651 2161 2635 763 3308 1222 4909 4547 8726 1023 1647 2394 8871 7949 8000 3432 9890 3204 5601 522 7080 4197 6196 1823 9215 921 8280 1458 6772 224 7778 2642 6537 6123 9356 5526 8250 1553 4583 7458 9120 4620 9415 1187 7963 2865 6165 3875 7048 512 2029 5059 9535 120 292 2555 7850 1281 4642 2116 2595 5697 9027 1110 2849 2669 7195 5792 7971 5284 6383 5477 7214 1040 1068 1292 1924 4745 8421 298 8964 181 8767 1974 9308 213 9189 2749 6797 1659 6339 1974 3184 3293 7170 2579 3675 3528 5224 7344 7903 1316 2973 1656 2546 2179 8484 853 2483 8851 9253 5334 9903 2507 6510 397 6023 4001 4276 2991 4752 7036 9593 834 2752 3630 7285 264 6617 2229 9401 1884 8167 597 1967 7175 8210 3133 9031 4510 7622 7796 9388 1679 7440 6979 7594 6314 8590 4141 9103 712 6940 3273 7804 2812 4576 1587 1643 1815 6520 1452 2903 6975 9170 4307 4967 2077 9042 1103 7733 343 4192 1607 3604 2464 7630 8453 8745 1078 2232 2072 9895 6777 7904 6484 8348 5527 9036 2445 5718 2505 3983 612 858 6009 7168 2128 8678 5841 6588 4085 6881 5016 9366 99 4946 1545 6405 8001 9165 4071 4749 5171 7772 1503 3965 1753 2155 5711 9080 7483 7668 664 7157 521 2293 136 4034 2260 9970 9469 9781 6259 6808 4482 7177 6658 9885 154 4009 1674 6674 6880 7883 1890 2537 7885 9826 2154 7466 8544 9816 2246 6686 1027 2234 1726 3497 7229 9991 1908 2006 2530 6829 2345 9832 571 9154 369 3417 247 564 4812 9565 1225 9388 2945 3186 5151 7954 5429 9305 2675 4564 3219 6317 1901 2444 6085 7503 3088 7321 1615 4372 6441 8537 5983 9115 1129 2491 518 1167 4218 4668 1910 8431 2446 9537 8788 9812 2678 7885 4323 5759 5375 5861 5585 5637 1241 7510 6853 7412 2962 9459 5974 7898 4340 4602 4000 9926 3485 5509 1859 5822 1003 7289 1572 5050 3378 4489 7103 9498 5442 9697 1564 1925 2689 9148 2801 5202 1895 8411 5851 8584 3154 9402 2605 4612 4842 8151 4047 8164 2110 8294 108 7793 7518 9256 207 1463 2782 3387 2733 4698 2875 6856 3698 8840 659 6017 2739 9222 643 5565 805 1936 1648 2909 8928 9271 8 2243 7535 9572 996 2024 7410 9127 2428 5792 4892 4961 1880 6286 1053 7092 5517 6167 3806 9071 494 731 4192 5208 245 2324 420 9928 4130 5876 6035 8254 870 7110 2414 9272 1633 6520 1310 3464 5134 5831 2370 9535 764 3291 2253 8842 3494 5453 3219 5624 8286 9884 4062 7857 2309 9337 3518 7436 2451 2485 5035 9381 279 4541 2212 7639 3001 8563 4661 7197 1462 9723 356 1361 2540 9324 218 2640 2269 3348 2188 3415 8335 9707 7150 8193 1254 2279 5802 7748 343 7341 214 2589 2790 6303 1961 6074 4116 9967 4211 7053 1581 4084 8710 9136 7622 9221 276 5029 932 1003 131 5187 7052 7691 184 606 497 5048 63 5754 1047 2755 5046 6692 5924 9032 2660 8696 1582 3875 440 3014 2202 7273 301 632 1917 7394 4083 5985 1976 2308 2318 7589 1833 2024 28 4650 1436 4163 4454 4579 255 1962 4593 4837 183 8068 1722 4046 696 3644 5101 7391 3589 7029 2930 3362 760 7741 6185 6820 3733 8691 1433 6849 2335 7545 2522 6820 3920 8305 883 5054 3353 9112 8313 9373 730 7464 1319 2895 2354 3178 3994 4369 3718 9965 2500 2653 5840 9484 5374 5427 1033 1228 41 2915 1015 8598 2601 8118 935 7464 3746 8044 3753 9242 3787 8751 1670 5705 5752 6415 1660 7246 3575 8307 5222 9274 262 6549 1666 4098 4599 9770 4372 7004 1837 7755 1383 2920 454 1283 2945 9221 8248 8907 4070 7096 2320 7459 1079 6221 1622 3237 5254 9062 2652 8206 3365 5500 7602 9954 2023 8231 7535 9615 2069 3125 3192 9798 4276 9834 3665 4185 1429 4598 2406 4408 5174 9772 2616 7881 1165 7219 1317 3195 912 3013 4937 7920 1824 6916 1438 1998 2692 7141 5175 9936 3030 7790 167 8168 470 9333 36 8705 2732 8654 4633 6213 4878 6337 1492 4046 611 5506 5624 5793 1312 8562 2317 8428 4672 6475 63 5732 3701 7984 3528 4917 176 254 1539 5639 7699 7826 2716 9435 9288 9901 2274 4052 3760 6471 1549 5658 1213 1986 720 6595 641 8740 2808 3266 3348 4210 4874 8093 1539 3136 227 5180 2266 6685 896 7167 244 4090 3159 6891 272 2859 1267 9888 2285 6106 3909 7500 747 6663 836 3947 158 2879 3647 5884 1347 1472 296 5521 5020 7718 1029 7449 1603 6476 2263 4265 1905 6289 5845 6623 5790 6191 4306 6549 2042 3431 5431 5609 1673 9299 1577 3509 2370 3513 5660 9296 2468 5457 2168 5570 5040 9219 8311 9889 664 1598 2244 8390 4802 4882 3780 9884 1709 7244 541 7845 4676 8256 3191 7260 9694 9791 6813 9043 3155 3179 9803 9986 1205 3269 3857 9721 1721 3739 1248 8096 4053 4201 2341 5866 8624 8901 405 2782 1064 5738 6005 6622 1109 7260 1725 5870 1184 7974 8915 8960 665 5517 ===OUTPUT=== 37 ===END===