===INPUT===
3
1000 10
6843 9976 2678 2382 9243 5061 3701 6333 3130 600 1790 8857 4420 745 1950 7607 847 5544 669 8338 3737 2699 1101 3664 4768 1788 9396 1350 4561 2172 2295 5822 8418 301 2728 1255 6676 7870 2626 9934 4355 7367 5489 5308 992 1368 4280 6832 225 8094 989 4943 4039 8710 7767 6473 1696 388 4603 558 2718 1238 7555 2112 8409 2196 6545 8922 1904 1995 7955 498 4469 3675 4711 2763 3546 910 8640 6382 5990 8778 3945 2521 9692 1080 7034 5369 9774 3925 7705 4133 8094 1529 7554 2778 7350 6087 6586 1742 2345 3380 48 1295 776 268 9878 8140 6745 9729 3839 4183 5942 2389 585 9513 6338 8314 7116 1126 5489 6663 9635 227 7192 2350 9803 6245 306 5596 3562 4699 4629 321 2211 4447 6181 2161 5206 5289 7 6074 1628 9781 713 5222 4052 8518 1600 1267 872 1675 8161 8834 2356 5616 1268 2589 1991 7640 3478 1388 1978 8010 1838 9002 2385 2618 6418 7571 400 2217 9195 3312 5633 7727 9303 6775 211 9064 9549 8685 3028 1645 7174 4941 1618 5077 6330 7326 3678 939 360 95 7362 6050 9035 5190 4853 710 57 1754 1724 9397 3853 4397 1347 1422 5240 814 8717 3144 707 8894 4024 7286 3048 2690 3125 4777 3762 5688 4599 6199 5586 9853 3497 2891 7731 2542 2372 3549 8496 398 8161 8692 1045 2936 4444 9273 3188 9845 251 1373 4809 5343 7870 5389 831 4055 214 5045 2468 7460 3594 5715 1082 7534 5192 6766 5888 9834 6809 2663 8737 8998 8024 7198 8747 2120 8004 5768 5107 2338 6516 2367 3575 4904 7051 3291 1171 2517 3405 8672 7800 4779 5216 6167 1610 8745 1046 66 3449 962 202 5658 7843 3484 7880 635 6919 3030 6979 1475 4093 6573 3009 3367 5172 5729 7625 4406 3084 1988 9777 2610 1558 4899 353 3708 7529 3367 684 3183 4038 9406 927 1760 8478 9590 5322 7188 1970 1866 6496 9203 538 8496 7946 1307 1450 2161 4128 7160 5651 1723 7434 3507 7526 196 2836 6105 4799 4480 9217 2365 8799 2069 8609 6896 8905 3485 3430 1968 2290 4411 3555 607 7667 1090 1638 54 9008 8130 4664 1593 782 3108 5506 2172 3169 936 5602 1670 2211 2204 8318 6325 4252 2672 3672 1379 4686 8377 7379 1480 2720 7107 5333 655 4302 6074 1582 397 895 2682 5816 9983 3223 101 1374 1876 701 4197 7298 6492 3087 4323 7914 702 7205 5592 5019 3296 2516 7905 2297 226 1781 8744 878 4860 7637 3905 2905 5594 6605 7218 7736 6228 6084 9863 6217 4515 3252 7716 141 2737 186 3965 1726 833 5378 4786 5123 1279 6387 5519 2642 8568 5511 3235 9413 9277 9390 1007 5152 7524 387 1026 6289 6464 7007 1058 2233 7218 1468 1581 4826 352 5260 1921 1730 676 1244 9337 4935 40 5891 7865 5587 2098 864 9612 9267 3274 9651 844 2730 531 4633 1281 6443 1209 4766 3853 9878 8504 4143 1000 8386 894 1198 3256 925 9426 8185 8980 1744 4836 3452 3096 4871 7798 4006 9259 1711 9532 1338 2847 10000 3120 9256 1977 3341 457 971 4386 3401 2125 7587 1837 8029 933 3718 4538 568 432 4338 266 3014 1466 7095 868 8020 2350 8627 1447 2658 8506 205 2417 7881 6258 7846 4992 9536 3048 7293 3063 5306 7690 9026 1235 5602 7580 8605 8303 4010 6744 1520 404 3616 6275 7674 6805 5282 4897 1021 5034 9891 9500 4835 4763 1086 2305 3213 95 6683 1132 1003 3493 1888 38 435 2532 362 1259 7243 5822 1788 2801 6297 8954 294 4453 6110 8034 3466 3208 3310 2298 1371 9595 2180 2755 4279 3318 147 6638 9383 175 9439 9092 468 937 7469 1414 8972 1243 3849 2641 997 1043 6151 7828 7202 8970 1692 5957 403 4746 221 9568 9698 9181 3720 6305 6987 1048 7122 4629 1339 7880 8304 940 3853 3548 538 3154 9969 1811 8237 3038 2526 6999 545 9594 5897 3338 1002 2404 9415 6671 6770 6596 2111 1965 2071 4063 1459 8639 1824 891 1968 6336 6134 7157 1412 6261 8193 6447 9296 3323 3057 30 2751 1427 926 3635 2582 9915 1762 6248 379 3072 8885 5485 3258 9424 9913 3411 966 8932 1159 8442 4254 2638 1529 4598 3537 8863 6506 6807 7538 1148 1019 2601 7375 7554 9656 2760 862 3303 6218 2328 6969 2195 7246 7925 2429 1888 5526 470 9805 4462 4014 1576 9660 7194 8689 8856 8875 831 7997 4864 5455 5037 437 6774 2054 1689 3846 6593 6220 2486 524 6990 2809 1987 3445 6258 9086 7460 4486 5633 6064 1925 2957 5246 3219 3724 1879 7027 7098 5807 1634 4675 5678 6982 2454 1775 9006 914 7056 5414 7078 3150 5359 5312 851 7317 3826 7949 1797 4788 6273 2489 8854 482 9772 5059 8442 9261 9265 2175 1671 7126 5602 1576 1016 2288 6581 8330 4236 932 2062 9087 964 905 9770 3880 5069 9987 1181 46 9307 1369 4895 6137 5543 5147 5459 673 5178 1380 8008 1635 1546 7820 7299 9863 3380 5106 6860 1440 9243 7144 2552 8131 2815 8062 2871 8012 7698 5956 4751 7485 4999 2474 9961 5943 4524 1707 7466 5166 3450 969 6404 5945 2234 5082 574 5112 7626 1828 8466 6537 9313 4645 5270 9883 511 1318 2141 8996 9224 3648 5758 321 2434 3920 6677 7245 7981 1799 7993 1204 691 6693 1118 5447 272 263 8491 9090 484 3230 6639 1628 758 2691 2336 2336 5499 6840 2356 5162 9464 8416 1875 963 1508 7601 3085 4113 3585 2297 152 6569 669 3295 572 918 4915 7180 6099 382 6088 9561 9451 9619 915 234 622 1367 4940 7948 3892 5268 953 7003 7223 9707 596 3191 7287 2124 8337 1464 9039 6933 8399 1599 4328 4638 284 3807 2124 2692 3214 2684 7806 3220 8144 7619 3448 4139 7865 4666 
1000 10
2725 7884 19 8617 672 9201 1643 6442 8525 2821 1956 2796 8966 7554 2465 7438 4777 3159 4915 586 4512 380 8047 9472 976 3880 9060 421 6119 9539 715 4171 7663 4776 6784 6627 2008 7213 2304 3648 7797 7558 7955 5646 7926 4342 4396 2723 4374 9000 4975 3812 422 7390 1411 5644 8297 1783 1304 5608 4849 7734 7338 3110 346 9217 6854 6864 2998 6631 9340 7187 2777 5349 3638 4597 1429 2795 7592 7142 6713 3418 3817 550 1765 5553 4305 4696 1938 313 9075 2613 607 9549 685 6980 5247 446 2397 3784 4625 5462 9686 1674 2896 2251 4564 1161 3133 6295 92 9232 7145 1941 1352 3719 3063 6286 6834 6204 6897 2662 2062 9491 810 928 9420 1819 9668 4745 1070 4308 7091 4067 2151 6110 8722 288 7317 1011 1444 579 2881 8072 4926 3297 4053 1471 4659 8893 9277 7521 1007 5221 3744 9530 2089 167 1312 9749 6514 4360 7089 5051 4275 694 1255 1734 887 2988 9507 6746 3988 9270 6047 7750 6608 486 8343 3351 5041 566 6555 9310 3237 8655 8626 179 291 682 8769 7898 1522 276 157 6789 2041 5943 2317 8634 5623 5383 9763 662 2068 5578 9853 6738 4343 5244 7207 1366 4681 8081 995 5547 7081 6828 6700 5813 7714 3776 9910 9472 3258 2213 6538 1690 5469 5534 9138 4674 1994 5704 7744 1984 6203 3365 9203 2981 3115 810 7420 8916 499 6102 9566 753 1637 644 4517 7736 3101 338 6424 8225 356 1395 7986 2691 8855 306 4621 1031 6360 1992 4128 6863 1667 8848 874 6038 3508 3625 1247 1865 8631 1644 3876 8295 8831 4207 9653 9717 7179 9144 2943 6757 5351 550 7274 5815 7407 6220 1847 7728 8985 2719 619 5611 1875 595 4586 6014 6170 9937 1976 238 4429 6844 2940 3781 1729 8660 710 1379 2662 1322 1506 9906 9770 8373 6509 2319 3853 4356 5767 4262 7429 7861 9946 8237 531 2294 1930 8019 117 3658 2222 3754 2461 1726 5950 8900 2386 5580 1773 346 405 5888 3257 8594 1815 7833 7745 385 4601 8146 1510 1743 2084 1666 5860 4443 9483 5521 9139 1551 8893 1276 4554 6294 975 3130 1203 1418 2298 6351 725 8402 6016 4209 5053 2588 4213 5098 9598 5128 8044 6142 6076 1830 8943 4349 371 8095 2563 4203 2621 5578 9947 9710 867 1432 5740 4087 1635 6882 4721 21 4772 1492 7087 5542 7318 1129 5292 3376 1709 3049 6252 4783 3872 3952 9596 7632 2044 9985 2819 157 3423 683 5253 7385 5778 6906 666 4447 8662 4145 1278 982 8306 5255 4891 8728 8955 5072 1748 9075 4742 3118 514 2863 9482 6391 2933 1969 7706 600 5283 2015 4465 2458 7925 4229 3230 148 4418 9176 1730 2609 3659 5753 2280 2260 7146 492 5205 8585 7573 2874 7616 3998 6871 1524 6595 7970 6208 3785 9666 1820 5899 4601 1612 8111 8369 8906 5424 2748 4877 8363 4306 7753 4688 3432 4206 2001 3557 2685 1483 8076 2359 1422 3044 8513 9505 2567 9075 2521 9511 9311 9567 757 2596 4019 7064 9859 5363 1584 48 1532 833 9984 652 5602 8947 1849 7083 8136 276 6738 614 1570 8530 5639 4761 880 122 4607 5425 5492 5760 2445 4535 3148 5284 5332 1500 460 7745 8398 1349 1948 8600 4366 744 2722 4925 9269 2167 9553 8208 274 62 7634 4110 2413 4760 3314 6873 9686 8790 108 7941 1353 8258 2728 4788 4885 9169 8757 7189 6990 7367 9138 8169 4191 3664 8995 1174 995 4508 6530 6399 2198 9162 2613 7187 136 6056 9423 1589 9426 2490 2905 7405 1244 7145 1857 9453 2446 30 6899 966 3734 8863 5176 8747 25 1433 4845 6310 3837 2944 3509 8651 2070 7426 6161 1450 3167 5458 6975 8088 7804 8948 961 8336 7758 6932 9824 5765 2903 3148 7584 9180 2047 3157 1829 8760 7557 7950 6775 4550 569 7339 162 7978 7338 1775 6784 6185 140 798 8971 9401 6684 3532 7438 7750 5271 8842 5612 4966 7960 4994 1283 7535 240 5825 2258 3079 2059 1748 1833 5708 9937 278 7551 1078 7802 1001 7994 746 1189 8163 7034 5008 5818 6251 503 2727 7967 5124 669 279 2744 2217 85 1799 1971 6233 7622 5792 2227 1542 7611 2434 490 3672 3670 9398 2845 1303 9381 7315 6883 4665 8021 3605 4542 6217 4405 5947 461 1817 2300 3071 9201 3337 1085 572 8558 2008 4937 203 6340 7914 5014 7438 1215 7690 8975 5297 2508 9058 5547 910 7598 1210 7411 5872 79 8253 2238 8458 8874 3218 5808 5000 2697 4281 7459 8054 1130 4564 915 1600 2264 8856 5489 1802 5367 3524 5312 5889 1951 6978 5476 7681 6909 6955 8684 633 9239 3520 6573 5836 830 182 7889 3097 2649 5618 7391 4045 8479 805 7501 3415 1285 7001 6564 3901 2169 3389 4227 1965 5918 718 390 8310 2666 2087 1176 9768 2252 1657 4359 4793 2689 6286 2167 7450 7432 2555 682 5641 1973 6965 2494 9368 7044 7925 3543 478 7887 526 6959 1837 9809 3342 7595 1844 8683 580 6688 533 3398 3105 4790 2105 5083 8898 1963 755 3936 477 2139 1075 3412 1993 8927 4092 5533 771 579 3879 1983 9198 6141 6425 5839 9787 4938 7395 281 1898 6715 4937 383 4016 3137 7381 9075 1945 4756 1532 5239 2175 5418 5873 1635 8635 1222 1433 7863 3164 1295 975 2658 1926 6868 2473 2418 2397 3580 9675 8748 4834 6914 4202 494 7949 752 3059 3 2076 7723 8141 6775 4010 1952 1164 3147 3427 9038 9992 268 9063 9236 9774 2383 5022 5628 2101 2000 5387 7992 6228 2411 900 7099 3233 1674 7568 6764 9949 7473 2498 7735 4766 3558 6357 3716 909 9796 1161 652 3746 6866 2605 1881 8348 2368 5821 4141 2181 4930 8686 3190 7430 5568 5399 2320 1687 8684 2947 3612 
1000 10
6153 4293 1908 3056 967 4028 394 8766 1898 1094 7652 4042 2493 8594 8102 3862 369 2555 2683 5520 6034 9439 1325 7502 2025 8481 4660 9017 130 6940 4331 1512 8145 4777 8329 1646 1057 675 238 2935 9293 3593 2508 6879 5875 2580 3433 2051 2341 1625 4994 2572 6194 3345 4209 9801 3285 8455 1570 7788 6652 1442 6611 2297 9691 1972 2506 8394 8562 2177 4651 3670 5549 7044 8058 3763 9354 7231 7726 9401 3600 6994 391 2265 4414 5118 3954 2270 5618 3226 6202 7235 252 613 6544 2806 5697 5965 1742 7883 692 1264 9801 7891 8722 8241 8726 3454 3772 7149 3678 2175 6315 350 7541 8496 1663 2815 6279 406 3496 338 6259 1813 1913 4159 1069 5959 1130 4509 8831 8857 9405 1318 3727 4135 9699 4406 1655 4409 4720 6516 6929 9950 5484 2116 1665 392 9819 2380 7080 7480 4224 534 6630 8443 9069 742 1760 9684 1022 2396 3122 9757 7575 844 7414 8713 4970 2572 7782 2012 7006 1869 4990 4540 1708 5918 6246 2937 8284 2109 4126 2844 704 3295 8763 972 8367 307 2065 3526 8773 5922 2225 414 56 697 8182 1249 3854 202 9066 5805 9118 400 5550 4915 8420 2418 250 9116 2905 2650 2593 9162 5905 5142 7897 176 5671 1758 1145 4805 7847 4583 4772 5892 6458 6855 9062 1911 5735 4570 8492 7798 1527 1653 937 2283 1882 1017 9205 536 5977 842 5064 9643 1164 3025 7529 6528 3293 8046 7264 4151 7308 2146 418 2648 4532 412 2190 9716 8365 3378 67 4158 1155 4755 2581 8394 3960 4315 6896 8501 6246 2038 8764 8038 7880 936 6642 1890 8297 7245 3325 9974 9052 1116 9844 6833 4013 7585 9879 5919 9560 5835 1592 750 6906 9491 397 6618 3812 4719 3667 1244 7207 7782 5557 1411 3052 8837 6317 7825 5891 8081 9641 9529 7807 2733 1986 1527 6623 9710 6313 625 2736 8189 819 2060 1362 766 7863 5331 4504 5071 2581 2227 3268 1970 7482 7370 978 8190 353 5586 8803 8867 6700 5080 1133 9741 5107 6738 7761 475 5851 4481 1374 4352 363 579 9092 5834 4172 8987 859 5249 6031 5237 3589 8082 8451 2372 9857 6428 3575 3359 3441 5803 4092 508 4958 3620 7423 2171 4811 8688 4726 1447 4552 8044 5561 2952 1112 4303 7619 7052 8837 8334 6360 359 3778 253 9785 7881 2416 8023 4598 3487 5429 208 4356 4700 9739 4585 3711 6153 1605 8276 9346 3259 9719 8952 5540 9989 422 3671 6677 605 4462 1678 777 8003 8659 7741 7444 8671 9753 7879 5831 5242 9608 220 9130 7089 9834 4357 2539 5013 1191 1056 5221 502 6084 5501 453 9425 935 6552 4457 5735 2126 1369 3674 6576 3968 9384 7563 5600 259 5172 2402 361 7264 165 231 8721 1365 624 7962 6470 5833 1196 3578 1535 6757 7619 8707 8692 4081 683 8712 7377 749 2230 8770 1415 8497 1911 5383 7299 6230 3349 8766 9203 1671 1188 6882 118 4354 8114 5061 5172 1476 5216 4743 8030 4916 3970 9735 2151 2206 3385 1833 5475 387 590 809 6478 3646 7169 9087 5713 1722 9060 4868 128 2547 5089 7412 6183 8891 1987 8243 8231 1582 7524 6453 2204 6567 1954 9529 3857 9636 2631 1925 6053 3928 5977 2792 959 1104 6592 8732 8864 4696 7687 1675 121 8830 484 3092 6829 5126 4443 9101 1384 7760 2111 3851 2352 552 474 9568 9258 2685 8752 7892 8448 1556 495 5975 8210 6237 5034 9014 9786 7638 1655 6716 3093 3134 3876 9835 2511 8813 3649 4091 2830 6371 9162 3954 4546 1310 7172 5124 3499 5808 4426 4349 2539 4591 1144 941 1277 862 6936 4804 359 1405 3819 238 956 5597 2427 5424 5301 1303 9278 9620 7697 2989 7373 3953 938 6113 1190 6959 1419 3748 2991 553 8750 4418 4732 995 7370 1548 9090 5614 238 2453 6845 1818 5943 7266 2879 5052 9512 4012 6970 8656 810 6872 4400 5681 1457 2296 7641 5158 2018 2163 7365 3167 818 2483 4034 465 625 5774 8944 2829 5159 4535 3827 984 3821 8405 1561 6855 5535 3956 9405 5193 8384 2026 7483 5609 2110 5565 3141 5300 1224 5924 2821 728 5790 8603 3331 5774 4872 5771 3530 777 1402 9769 2134 2127 6214 1262 993 2536 7074 3751 2462 4244 6331 605 3445 386 9450 1687 5809 6751 1894 1887 822 6411 4027 5427 5639 7762 873 7453 4999 2889 256 7573 638 2360 9978 4533 510 2279 8377 541 3527 6316 7492 5048 9768 5764 572 2030 9734 4367 2115 588 1346 6337 6431 5665 2710 2134 3547 8715 6160 5542 160 1265 1411 7050 594 6130 1802 9838 7005 8142 1486 1239 7170 1475 9050 7670 1420 795 3277 9565 3064 4547 3327 8498 4452 399 2264 7314 279 1132 6637 1448 9026 5927 6332 8126 6005 413 9979 7442 1061 2130 8428 1565 6525 9685 6244 2209 2946 2244 3532 2017 6684 5500 2518 2757 2849 772 4596 8285 9844 1034 3942 9030 3614 542 4947 8539 3852 3726 9738 3662 1962 6449 6249 6407 7485 7000 1421 9052 2183 1778 795 7954 775 1631 2559 4690 9695 759 4899 2752 714 1196 3475 8584 8461 8621 3838 6730 3166 6093 8127 7240 1666 644 45 5901 5067 8883 7007 9120 3938 2093 5172 3560 1137 7572 9442 8979 3605 9938 5405 514 8290 842 219 5047 1415 2046 1094 466 2675 9522 2850 4328 983 1553 6415 8438 5054 1086 3312 4132 9100 5950 7197 4349 9427 7172 4279 4941 9275 716 9850 1324 7666 5644 4280 763 6402 5528 5235 7468 803 2470 1194 183 193 4385 7928 3434 1855 4737 5770 7057 1867 11 4448 6855 5300 9029 3301 2075 9178 8333 5170 4262 8101 3258 6416 2715 7896 9379 7357 7552 7367 5375 8336 5773 6727 9949 1424 4099 6805 1253 4931 1662 1449
===OUTPUT===
1100
1096
1103
===END===