#include <bits/stdc++.h>

using namespace std;

int result[] = {
	0 ,
	1 ,
	6 ,
	11 ,
	10 ,
	34 ,
	27 ,
	2 ,
	44 ,
	1 ,
	55 ,
	90 ,
	54 ,
	126 ,
	16 ,
	119 ,
	21 ,
	88 ,
	8 ,
	19 ,
	141 ,
	54 ,
	56 ,
	71 ,
	106 ,
	64 ,
	69 ,
	27 ,
	72 ,
	55 ,
	135 ,
	47 ,
	168 ,
	161 ,
	137 ,
	79 ,
	64 ,
	309 ,
	123 ,
	332 ,
	307 ,
	8 ,
	254 ,
	83 ,
	448 ,
	109 ,
	27 ,
	519 ,
	567 ,
	2 ,
	259 ,
	107 ,
	225 ,
	269 ,
	216 ,
	118 ,
	90 ,
	316 ,
	164 ,
	503 ,
	1015 ,
	333 ,
	181 ,
	47 ,
	857 ,
	6 ,
	704 ,
	63 ,
	385 ,
	253 ,
	343 ,
	604 ,
	457 ,
	144 ,
	79 ,
	90 ,
	984 ,
	656 ,
	351 ,
	164 ,
	595 ,
	729 ,
	64 ,
	160 ,
	503 ,
	128 ,
	269 ,
	495 ,
	1017 ,
	531 ,
	872 ,
	163 ,
	216 ,
	133 ,
	235 ,
	287 ,
	361 ,
	426 ,
	16 ,
	379 ,
	531 ,
	510 ,
	856 ,
	138 ,
	719 ,
	161 ,
	623 ,
	1259 ,
	610 ,
	190 ,
	34 ,
	279 ,
	720 ,
	1178 ,
	1322 ,
	27 ,
	350 ,
	1231 ,
	776 ,
	1104 ,
	729 ,
	155 ,
	1069 ,
	92 ,
	109 ,
	1133 ,
	376 ,
	127 ,
	521 ,
	370 ,
	48 ,
	438 ,
	125 ,
	198 ,
	134 ,
	17 ,
	209 ,
	386 ,
	729 ,
	307 ,
	1563 ,
	269 ,
	651 ,
	260 ,
	1 ,
	144 ,
	1063 ,
	34 ,
	632 ,
	701 ,
	557 ,
	434 ,
	1546 ,
	848 ,
	873 ,
	1403 ,
	20 ,
	174 ,
	307 ,
	27 ,
	2233 ,
	315 ,
	2387 ,
	2 ,
	403 ,
	603 ,
	1280 ,
	88 ,
	961 ,
	92 ,
	423 ,
	2027 ,
	1 ,
	413 ,
	1288 ,
	226 ,
	1276 ,
	252 ,
	2783 ,
	1095 ,
	1205 ,
	405 ,
	1304 ,
	2081 ,
	1126 ,
	414 ,
	981 ,
	524 ,
	1429 ,
	369 ,
	100 ,
	190 ,
	2888 ,
	57 ,
	1205 ,
	162 ,
	128 ,
	701 ,
	1548 ,
	55 ,
	1752 ,
	298 ,
	405 ,
	2016 ,
	721 ,
	461 ,
	125 ,
	2927 ,
	1603 ,
	2185 ,
	1288 ,
	118 ,
	330 ,
	631 ,
	450 ,
	153 ,
	97 ,
	9 ,
	646 ,
	2619 ,
	272 ,
	2906 ,
	2133 ,
	335 ,
	980 ,
	92 ,
	1009 ,
	1126 ,
	3095 ,
	3989 ,
	216 ,
	604 ,
	560 ,
	288 ,
	6103 ,
	29 ,
	6 ,
	1422 ,
	1296 ,
	1711 ,
	3977 ,
	470 ,
	161 ,
	803 ,
	1513 ,
	250 ,
	736 ,
	855 ,
	159 ,
	64 ,
	1558 ,
	216 ,
	441 ,
	93 ,
	1016 ,
	575 ,
	729 ,
	1286 ,
	11 ,
	1458 ,
	384 ,
	378 ,
	1810 ,
	1322 ,
	1000 ,
	3324 ,
	873 ,
	2663 ,
	1072 ,
	277 ,
	136 ,
	468 ,
	36 ,
	540 ,
	2025 ,
	766 ,
	720 ,
	525 ,
	1455 ,
	1414 ,
	1106 ,
	3555 ,
	225 ,
	739 ,
	601 ,
	4256 ,
	2080 ,
	1513 ,
	8 ,
	857 ,
	1152 ,
	325 ,
	2619 ,
	512 ,
	272 ,
	3494 ,
	1891 ,
	323 ,
	1989 ,
	197 ,
	1756 ,
	658 ,
	3472 ,
	1550 ,
	1712 ,
	2409 ,
	271 ,
	6544 ,
	1645 ,
	343 ,
	631 ,
	169 ,
	160 ,
	1854 ,
	1392 ,
	4347 ,
	2052 ,
	2141 ,
	216 ,
	1855 ,
	314 ,
	277 ,
	2261 ,
	1539 ,
	233 ,
	685 ,
	16 ,
	783 ,
	3224 ,
	539 ,
	101 ,
	316 ,
	15 ,
	2836 ,
	704 ,
	566 ,
	6041 ,
	190 ,
	736 ,
	747 ,
	27 ,
	1005 ,
	209 ,
	532 ,
	8 ,
	560 ,
	125 ,
	2276 ,
	1546 ,
	174 ,
	350 ,
	71 ,
	2919 ,
	657 ,
	1639 ,
	1728 ,
	2581 ,
	1538 ,
	1387 ,
	7658 ,
	1035 ,
	864 ,
	3030 ,
	2972 ,
	3493 ,
	413 ,
	4733 ,
	1811 ,
	294 ,
	721 ,
	839 ,
	3736 ,
	1000 ,
	3717 ,
	771 ,
	1945 ,
	146 ,
	2357 ,
	27 ,
	128 ,
	800 ,
	613 ,
	83 ,
	2143 ,
	2241 ,
	2 ,
	456 ,
	1459 ,
	83 ,
	881 ,
	889 ,
	20 ,
	1024 ,
	190 ,
	359 ,
	879 ,
	1981 ,
	973 ,
	440 ,
	191 ,
	4249 ,
	577 ,
	406 ,
	3340 ,
	287 ,
	242 ,
	252 ,
	1329 ,
	3059 ,
	6985 ,
	2023 ,
	2531 ,
	1000 ,
	2050 ,
	947 ,
	1325 ,
	1189 ,
	674 ,
	81 ,
	755 ,
	1594 ,
	183 ,
	944 ,
	4078 ,
	2332 ,
	475 ,
	1475 ,
	9246 ,
	1249 ,
	829 ,
	1224 ,
	4623 ,
	27 ,
	2339 ,
	72 ,
	818 ,
	911 ,
	665 ,
	1297 ,
	5060 ,
	907 ,
	918 ,
	255 ,
	2528 ,
	1295 ,
	21 ,
	2161 ,
	802 ,
	5286 ,
	4481 ,
	736 ,
	1028 ,
	827 ,
	125 ,
	2233 ,
	2058 ,
	4824 ,
	883 ,
	99 ,
	71 ,
	1728 ,
	125 ,
	1925 ,
	4412 ,
	4480 ,
	90 ,
	2304 ,
	2860 ,
	540 ,
	8325 ,
	232 ,
	4222 ,
	48 ,
	441 ,
	307 ,
	4347 ,
	989 ,
	729 ,
	2547 ,
	1392 ,
	1891 ,
	407 ,
	358 ,
	281 ,
	1288 ,
	610 ,
	2162 ,
	416 ,
	979 ,
	54 ,
	1008 ,
	1555 ,
	17 ,
	1819 ,
	1457 ,
	4591 ,
	901 ,
	1304 ,
	512 ,
	353 ,
	3312 ,
	163 ,
	936 ,
	3780 ,
	2464 ,
	1 ,
	171 ,
	2484 ,
	2611 ,
	810 ,
	83 ,
	3143 ,
	1899 ,
	2060 ,
	2069 ,
	3402 ,
	27 ,
	216 ,
	2123 ,
	64 ,
	3072 ,
	1736 ,
	421 ,
	1908 ,
	2384 ,
	4088 ,
	541 ,
	1023 ,
	621 ,
	353 ,
	594 ,
	243 ,
	6076 ,
	1717 ,
	2403 ,
	1847 ,
	2465 ,
	1306 ,
	1658 ,
	2662 ,
	1088 ,
	406 ,
	963 ,
	380 ,
	288 ,
	286 ,
	637 ,
	1107 ,
	303 ,
	4922 ,
	783 ,
	5068 ,
	1483 ,
	369 ,
	2402 ,
	3754 ,
	1189 ,
	3186 ,
	629 ,
	4647 ,
	4086 ,
	343 ,
	703 ,
	1826 ,
	1800 ,
	236 ,
	3372 ,
	7315 ,
	1702 ,
	1709 ,
	1331 ,
	2205 ,
	1096 ,
	1096 ,
	10172 ,
	3375 ,
	64 ,
	1 ,
	519 ,
	1208 ,
	2414 ,
	70 ,
	2600 ,
	11971 ,
	5138 ,
	1177 ,
	694 ,
	1646 ,
	2176 ,
	685 ,
	1932 ,
	349 ,
	3675 ,
	2545 ,
	2584 ,
	2044 ,
	2653 ,
	1485 ,
	1576 ,
	1799 ,
	2223 ,
	2070 ,
	3617 ,
	1675 ,
	5536 ,
	3534 ,
	729 ,
	1007 ,
	361 ,
	3682 ,
	6077 ,
	251 ,
	2168 ,
	603 ,
	1413 ,
	3394 ,
	2001 ,
	2484 ,
	2744 ,
	9603 ,
	5048 ,
	1798 ,
	1162 ,
	1554 ,
	1037 ,
	101 ,
	7021 ,
	7498 ,
	2315 ,
	873 ,
	225 ,
	1575 ,
	5361 ,
	740 ,
	1802 ,
	629 ,
	1728 ,
	1918 ,
	11931 ,
	3977 ,
	1838 ,
	449 ,
	2216 ,
	3450 ,
	6 ,
	2962 ,
	289 ,
	610 ,
	1331 ,
	586 ,
	991 ,
	243 ,
	128 ,
	1133 ,
	6074 ,
	5231 ,
	2799 ,
	1910 ,
	1890 ,
	171 ,
	808 ,
	2169 ,
	511 ,
	1394 ,
	120 ,
	4454 ,
	2675 ,
	1000 ,
	5632 ,
	1151 ,
	2358 ,
	4291 ,
	153 ,
	1099 ,
	1520 ,
	1728 ,
	1270 ,
	3247 ,
	5976 ,
	3719 ,
	216 ,
	10334 ,
	1674 ,
	10 ,
	1672 ,
	693 ,
	4256 ,
	2754 ,
	64 ,
	1432 ,
	4480 ,
	6726 ,
	854 ,
	2807 ,
	8991 ,
	1458 ,
	557 ,
	12440 ,
	1392 ,
	3287 ,
	937 ,
	5946 ,
	568 ,
	9927 ,
	3193 ,
	783 ,
	1253 ,
	411 ,
	162 ,
	694 ,
	6613 ,
	79 ,
	2395 ,
	1988 ,
	1591 ,
	3628 ,
	2311 ,
	5149 ,
	668 ,
	8322 ,
	125 ,
	1666 ,
	791 ,
	2080 ,
	9461 ,
	1403 ,
	3401 ,
	1413 ,
	8595 ,
	1 ,
	615 ,
	9755 ,
	3664 ,
	901 ,
	2204 ,
	4250 ,
	2352 ,
	430 ,
	4913 ,
	9738 ,
	538 ,
	1511 ,
	4599 ,
	4686 ,
	4293 ,
	3177 ,
	1968 ,
	1728 ,
	1565 ,
	1260 ,
	92 ,
	2 ,
	1168 ,
	4475 ,
	1560 ,
	4211 ,
	216 ,
	3368 ,
	1024 ,
	2511 ,
	190 ,
	7081 ,
	4904 ,
	251 ,
	664 ,
	1898 ,
	2199 ,
	3123 ,
	11311 ,
	216 ,
	16 ,
	2339 ,
	3648 ,
	2267 ,
	297 ,
	1071 ,
	664 ,
	4564 ,
	7048 ,
	1862 ,
	2500 ,
	541 ,
	160 ,
	216 ,
	2998 ,
	4159 ,
	1520 ,
	4555 ,
	2537 ,
	232 ,
	7032 ,
	4039 ,
	883 ,
	65 ,
	3184 ,
	3375 ,
	3520 ,
	5282 ,
	322 ,
	867 ,
	1177 ,
	137 ,
	729 ,
	15775 ,
	3248 ,
	2765 ,
	10249 ,
	2774 ,
	2296 ,
	7892 ,
	1936 ,
	4771 ,
	2016 ,
	722 ,
	10011 ,
	46 ,
	972 ,
	3638 ,
	1329 ,
	819 ,
	919 ,
	1429 ,
	2547 ,
	246 ,
	3205 ,
	2108 ,
	11324 ,
	835 ,
	3472 ,
	1728 ,
	4462 ,
	1098 ,
	9512 ,
	1808 ,
	3538 ,
	57 ,
	648 ,
	43 ,
	6040 ,
	2736 ,
	1357 ,
	2577 ,
	1464 ,
	11 ,
	1396 ,
	279 ,
	6075 ,
	2998 ,
	2051 ,
	7217 ,
	3800 ,
	700 ,
	6984 ,
	3205 ,
	1610 ,
	6973 ,
	4131 ,
	3777 ,
	3979 ,
	820 ,
	125 ,
	3268 ,
	5085 ,
	801 ,
	216 ,
	209 ,
	2323 ,
	874 ,
	576 ,
	9710 ,
	766 ,
	7391 ,
	6163 ,
	8775 ,
	2090 ,
	1223 ,
	4139 ,
	2549 ,
	3788 ,
	10226 ,
	755 ,
	7820 ,
	2009 ,
	10083 ,
	2040 ,
	3238 ,
	918 ,
	3375 ,
	5186 ,
	1666 ,
	168 ,
	1675 ,
	111 ,
	449 ,
	6416 ,
	3303 ,
	2744 ,
	3376 ,
	847 ,
	11617 ,
	5888 ,
	109 ,
	951 ,
	2016 ,
	1 ,
	1556 ,
	963 ,
	3817 ,
	7099 ,
	1322 ,
	91 ,
	19151 ,
	3277 ,
	1622 ,
	1205 ,
	810 ,
	792 ,
	4461 ,
	568 ,
	3699 ,
	4285 ,
	2941 ,
	957 ,
	3952 ,
	1442 ,
	4851 ,
	2575 ,
	3854 ,
	524 ,
	1951 ,
	531 ,
	558 ,
	8226 ,
	4446 ,
	2820 ,
	2787 ,
	2538 ,
	244 ,
	467 ,
	7372 ,
	883 ,
	2573 ,
	6499 ,
	1639 ,
	384 ,
	1496 ,
	281 ,
	1968 ,
	2456 ,
	1190 ,
	12156 ,
	3960 ,
	6013 ,
	3193 ,
	430 ,
	867 ,
	1052 ,
	677 ,
	6419 ,
	2105 ,
	8478 ,
	3018 ,
	117 ,
	7433 ,
	1243 ,
	4733 ,
	649 ,
	938 ,
	3193 ,
	5320 ,
	729 ,
	5649 ,
	1756 ,
	1773 ,
	2493 ,
	12519 ,
	2548 ,
	1583 ,
	432 ,
	2323 ,
	2042 ,
	2520 ,
	6966 ,
	224 ,
	99 ,
	5268 ,
	4256 ,
	1178 ,
	426 ,
	1591 ,
	2727 ,
	3782 ,
	2447 ,
	1618 ,
	1503 ,
	8 ,
	405 ,
	5121 ,
	2824 ,
	2871 ,
	1091 ,
	7856 ,
	1304 ,
	1603 ,
	2211 ,
	413 ,
	3340 ,
	5130 ,
	343 ,
	1604 ,
	1 ,
	3123 ,
	1368 ,
	762 ,
	3413 ,
	911 ,
	1899 ,
	3706 ,
	6480 ,
	6002 ,
	664 ,
	1604 ,
	943 ,
	17018 ,
	10109 ,
	314 ,
	2717 ,
	2548 ,
	6481 ,
	1171 ,
	323 ,
	3481 ,
	216 ,
	128 ,
	1071 ,
	10268 ,
	460 ,
	1169 ,
	512 ,
	4591 ,
	16766 ,
	298 ,
	1341 ,
	726 ,
	864 ,
	415 ,
	2357 ,
	4698 ,
	4367 ,
	4452 ,
	9170 ,
	2702 ,
	4328 ,
	1917 ,
	2631 ,
	287 ,
	4876 ,
	2235 ,
	2824 ,
	1737 ,
	118 ,
	3158 ,
	1944 ,
	10494 ,
	285 ,
	3123 ,
	8947 ,
	16827 ,
	541 ,
	9965 ,
	1771 ,
	2368 ,
	1386 ,
	3885 ,
	4367 ,
	9722 ,
	3814 ,
	8946 ,
	4429 ,
	4635 ,
	1009 ,
	2036 ,
	1260 ,
	153 ,
	7704 ,
	1125 ,
	3040 ,
	190 ,
	2304 ,
	304 ,
	2288 ,
	15378 ,
	5096 ,
	820 ,
	3193 ,
	2412 ,
	2424 ,
	4704 ,
	2864 ,
	1549 ,
	3697 ,
	854 ,
	181 ,
	17009 ,
	873 ,
	7497 ,
	2952 ,
	512 ,
	11341 ,
	9646 ,
	9485 ,
	13824 

};

int main ()
{
	int N;
	while( cin >> N , N )
	{
		cout << result[N] << endl;
	}
}

Measured memory_bytes: 1164