#include <iostream> #include <cstdio> #define ll long long using namespace std; inline ll read(){ static ll xx = 0, c=getchar(); for(;c <=47|| c >=58; c=getchar( )) ; for( xx=0; c>=48&&c <=57; c=getchar( )) xx=(xx<<3)+(xx<<1)+(c &15); return xx; } long long db[5010] = {0,0,0,1,1,1,1,2,3,3,3,4,4,4,4,6,6,7,7,8,8,8,8,9,11,11,12,13,13,13,13,15,15,15,15,18,18,18,18,19,19,19,19,20,21,21,21,23,26,28,28,29,29,30,30,31,31,31,31,32,32,32,33,37,37,37,37,38,38,38,38,41,41,41,43,44,44,44,44,46,50,50,50,51,51,51,51,52,52,53,53,54,54,54,54,56,56,59,60,65,65,65,65,66,66,66,66,69,69,69,69,71,71,71,71,72,73,73,73,74,79,79,79,80,82,83,83,87,87,87,87,88,88,88,89,90,90,90,90,91,91,91,91,97,97,97,100,101,101,103,103,104,105,105,105,106,106,106,106,108,108,112,112,113,113,113,113,114,120,120,121,122,122,122,124,126,126,126,126,129,129,129,129,130,130,130,130,131,132,132,132,136,136,136,136,143,143,144,144,149,149,149,149,150,150,150,151,153,153,153,153,154,154,154,154,157,157,157,157,158,158,158,158,160,167,167,167,168,168,168,168,169,169,170,170,171,171,171,171,173,173,178,182,183,186,186,186,187,187,189,189,192,192,192,192,200,200,200,200,201,202,202,202,203,203,203,203,204,204,205,205,207,207,207,209,210,210,210,211,212,212,212,212,213,213,213,213,219,227,227,227,228,228,231,231,232,233,233,233,238,238,238,238,240,240,241,241,242,242,242,242,243,243,243,244,245,245,245,245,249,249,249,249,258,260,260,260,261,261,261,261,262,263,263,263,265,265,271,271,272,272,273,276,277,277,277,277,278,278,280,281,283,283,283,283,284,284,284,284,287,296,296,301,302,302,302,302,304,305,305,305,306,306,306,308,309,309,310,310,311,311,311,311,315,315,315,316,317,317,317,317,324,324,324,324,327,327,327,327,337,337,337,337,338,342,342,342,343,343,343,343,344,344,345,345,347,347,347,347,348,348,348,349,350,352,352,352,353,353,353,353,359,359,359,359,360,360,360,360,361,371,371,371,372,372,372,372,376,376,383,383,384,384,384,384,385,385,385,386,387,387,387,387,389,389,389,389,392,392,392,392,393,393,393,395,396,397,397,397,399,399,399,399,410,410,414,414,415,415,418,418,419,419,419,420,422,422,422,422,427,427,427,427,430,430,430,436,437,437,437,437,445,446,446,446,447,447,447,447,448,448,449,449,450,452,452,452,454,465,465,466,467,467,467,467,468,468,468,471,474,474,474,474,476,476,476,476,477,478,480,480,481,481,481,481,482,482,483,483,485,485,485,485,486,486,486,490,491,491,491,491,492,492,492,494,506,506,514,514,515,515,515,515,516,517,517,517,524,524,524,524,526,526,527,527,528,528,528,528,533,533,533,534,535,540,540,540,542,542,542,542,545,545,545,545,546,546,546,546,547,548,548,548,550,562,562,562,563,563,564,564,565,565,565,565,566,569,569,570,574,574,574,574,575,575,575,575,584,584,586,586,587,587,587,587,589,590,590,590,591,591,591,591,592,592,593,593,594,594,594,594,596,596,596,603,616,616,616,616,617,617,617,617,620,620,623,623,625,625,625,625,626,627,627,627,628,628,628,628,633,633,634,634,638,638,638,638,639,639,639,640,641,641,641,641,642,642,642,642,648,648,657,657,658,660,665,665,666,679,679,679,680,680,680,683,685,685,686,686,687,687,687,687,688,688,688,689,690,690,692,692,694,694,694,694,697,697,697,697,698,698,698,698,699,700,700,700,708,708,708,708,709,709,710,712,713,713,713,713,714,714,714,715,729,729,729,729,730,730,730,730,733,733,733,733,734,734,734,734,744,745,745,745,746,746,746,746,747,747,751,751,752,752,752,752,754,754,754,755,756,756,756,756,757,759,759,759,762,762,762,762,766,769,769,769,770,771,771,771,772,786,786,786,787,793,794,799,801,801,803,803,804,804,804,805,806,806,806,806,807,807,807,807,813,813,813,821,822,822,822,822,823,824,824,826,827,827,827,827,829,829,839,839,840,840,840,840,841,841,841,845,846,846,846,846,850,850,850,850,865,865,865,865,866,866,866,866,867,868,868,868,870,870,870,870,871,871,872,872,873,873,873,873,874,876,876,877,879,879,879,882,883,883,883,883,886,886,886,886,887,887,887,887,889,890,890,890,891,891,893,893,894,894,895,895,896,896,896,896,900,915,915,916,917,917,917,917,928,928,928,928,937,937,937,939,941,941,941,941,948,949,949,949,950,950,950,950,951,951,952,952,954,954,954,954,955,955,955,956,961,961,961,961,962,962,962,962,968,968,968,968,969,969,975,975,976,977,977,977,978,978,978,978,994,996,997,997,998,1001,1001,1001,1002,1002,1002,1003,1004,1004,1004,1004,1006,1006,1006,1006,1009,1009,1009,1009,1010,1010,1012,1012,1013,1017,1017,1017,1019,1019,1030,1030,1031,1031,1032,1032,1033,1033,1033,1033,1034,1034,1034,1035,1037,1037,1037,1039,1040,1040,1043,1043,1046,1046,1046,1055,1056,1056,1056,1056,1060,1076,1076,1076,1077,1077,1077,1077,1078,1078,1079,1079,1084,1084,1084,1084,1086,1086,1086,1087,1088,1088,1088,1088,1089,1089,1089,1089,1092,1092,1092,1092,1094,1094,1094,1094,1095,1102,1102,1105,1106,1106,1106,1106,1107,1107,1111,1111,1113,1113,1113,1113,1114,1114,1114,1115,1116,1116,1116,1116,1117,1117,1119,1119,1131,1131,1131,1131,1148,1148,1148,1148,1149,1150,1150,1150,1151,1151,1151,1151,1153,1153,1154,1154,1155,1155,1155,1157,1164,1164,1164,1165,1166,1166,1166,1172,1174,1174,1174,1174,1177,1177,1177,1177,1178,1178,1178,1178,1179,1180,1180,1180,1190,1190,1190,1190,1191,1191,1192,1192,1193,1193,1198,1198,1199,1199,1199,1203,1207,1207,1207,1207,1208,1208,1208,1208,1211,1228,1228,1228,1229,1229,1229,1229,1231,1232,1232,1232,1233,1233,1233,1233,1234,1234,1235,1235,1236,1236,1236,1236,1238,1238,1250,1251,1252,1252,1252,1252,1253,1253,1253,1253,1256,1256,1256,1256,1258,1258,1258,1258,1259,1260,1260,1260,1261,1261,1264,1266,1267,1267,1268,1268,1276,1276,1276,1276,1277,1277,1277,1278,1279,1279,1279,1279,1280,1280,1280,1280,1298,1298,1298,1298,1303,1303,1303,1303,1304,1305,1305,1305,1306,1306,1306,1306,1308,1308,1309,1309,1310,1310,1310,1310,1311,1311,1311,1321,1322,1324,1324,1324,1326,1326,1326,1331,1334,1334,1334,1334,1335,1335,1335,1335,1336,1337,1337,1337,1341,1341,1341,1341,1342,1342,1349,1349,1362,1362,1362,1362,1363,1363,1363,1364,1366,1366,1366,1366,1367,1367,1367,1367,1370,1388,1388,1388,1395,1395,1395,1397,1399,1403,1403,1403,1404,1404,1404,1404,1405,1405,1406,1406,1407,1407,1407,1407,1409,1409,1409,1410,1411,1411,1411,1411,1416,1416,1416,1416,1419,1419,1419,1419,1423,1423,1423,1423,1424,1425,1425,1425,1426,1426,1426,1426,1427,1430,1431,1431,1433,1435,1435,1435,1436,1436,1436,1437,1438,1438,1438,1438,1439,1439,1439,1439,1445,1445,1445,1445,1464,1472,1472,1472,1473,1474,1476,1476,1487,1487,1487,1487,1489,1489,1502,1502,1503,1503,1503,1503,1504,1504,1504,1505,1506,1506,1509,1509,1513,1513,1513,1515,1518,1518,1518,1518,1519,1519,1519,1519,1520,1521,1521,1521,1523,1523,1523,1523,1524,1524,1525,1525,1526,1526,1526,1526,1531,1531,1531,1532,1534,1534,1534,1534,1535,1535,1535,1535,1538,1538,1538,1538,1539,1539,1539,1542,1544,1563,1563,1563,1564,1566,1566,1566,1567,1567,1568,1568,1569,1569,1569,1569,1577,1577,1577,1581,1582,1582,1582,1582,1583,1583,1583,1583,1586,1586,1588,1588,1590,1590,1590,1590,1591,1592,1592,1592,1593,1593,1593,1593,1594,1594,1595,1595,1609,1609,1609,1609,1610,1615,1615,1622,1623,1623,1623,1623,1624,1624,1624,1624,1630,1630,1630,1641,1642,1642,1642,1642,1643,1644,1644,1644,1645,1645,1645,1645,1665,1665,1666,1666,1667,1667,1667,1667,1668,1668,1668,1669,1670,1670,1670,1670,1672,1675,1675,1675,1684,1684,1684,1684,1685,1687,1687,1687,1688,1689,1689,1689,1691,1691,1691,1691,1692,1692,1693,1693,1694,1694,1694,1694,1695,1695,1695,1696,1698,1698,1700,1700,1701,1701,1701,1701,1704,1704,1704,1704,1705,1705,1705,1705,1709,1710,1713,1713,1714,1714,1714,1714,1715,1715,1716,1718,1719,1719,1719,1719,1721,1741,1755,1756,1757,1757,1757,1757,1758,1758,1764,1764,1767,1767,1772,1772,1774,1774,1774,1774,1779,1783,1783,1783,1784,1784,1784,1784,1785,1785,1786,1786,1788,1788,1788,1791,1792,1792,1792,1793,1794,1794,1794,1794,1795,1797,1797,1797,1809,1809,1809,1809,1810,1810,1818,1818,1819,1820,1820,1820,1821,1821,1821,1821,1823,1823,1824,1824,1825,1825,1827,1827,1828,1828,1828,1829,1830,1830,1830,1830,1832,1832,1832,1832,1853,1853,1853,1853,1854,1854,1854,1854,1855,1856,1856,1858,1860,1860,1860,1860,1861,1861,1865,1865,1866,1866,1866,1866,1867,1867,1867,1868,1876,1876,1876,1876,1877,1877,1877,1877,1892,1892,1892,1892,1893,1902,1902,1902,1904,1905,1905,1905,1906,1909,1909,1914,1915,1915,1916,1916,1917,1917,1917,1917,1919,1921,1921,1922,1923,1923,1923,1923,1924,1924,1924,1924,1927,1927,1927,1927,1929,1929,1929,1929,1930,1931,1931,1931,1932,1953,1955,1955,1956,1956,1957,1957,1961,1961,1961,1967,1968,1968,1971,1975,1976,1976,1976,1976,1977,1977,1977,1977,1983,1983,1983,1995,1996,1996,1996,1996,1997,1998,1998,1998,1999,1999,1999,1999,2001,2001,2002,2002,2003,2003,2003,2003,2004,2004,2004,2005,2010,2010,2010,2010,2012,2012,2012,2012,2015,2015,2015,2018,2019,2019,2019,2019,2020,2021,2021,2021,2025,2025,2040,2040,2041,2043,2044,2044,2045,2045,2045,2045,2046,2046,2046,2047,2069,2069,2069,2069,2070,2070,2070,2070,2079,2079,2079,2079,2080,2080,2082,2082,2084,2085,2085,2085,2086,2086,2086,2086,2093,2093,2094,2094,2095,2095,2095,2095,2097,2097,2097,2098,2099,2099,2099,2101,2102,2102,2102,2102,2105,2105,2105,2105,2109,2109,2109,2109,2110,2111,2111,2111,2112,2112,2112,2112,2113,2113,2114,2114,2124,2124,2124,2124,2125,2125,2125,2126,2127,2130,2130,2130,2131,2131,2131,2131,2137,2137,2137,2137,2138,2138,2138,2146,2147,2169,2169,2169,2182,2182,2182,2182,2184,2184,2185,2185,2186,2186,2186,2186,2187,2187,2187,2188,2189,2189,2189,2189,2205,2205,2207,2207,2210,2210,2210,2210,2211,2216,2219,2219,2220,2221,2221,2221,2223,2223,2223,2223,2224,2224,2225,2225,2226,2226,2226,2228,2229,2229,2229,2230,2232,2232,2232,2232,2233,2233,2233,2233,2236,2236,2236,2236,2237,2237,2237,2237,2239,2240,2240,2240,2245,2245,2245,2245,2246,2246,2250,2253,2254,2254,2254,2254,2258,2258,2258,2259,2282,2282,2282,2282,2283,2283,2283,2283,2286,2288,2288,2288,2290,2290,2290,2290,2291,2292,2292,2292,2293,2293,2293,2293,2294,2294,2295,2295,2297,2297,2297,2297,2298,2298,2300,2301,2302,2302,2302,2302,2309,2309,2309,2309,2315,2315,2315,2315,2316,2316,2325,2325,2326,2327,2327,2327,2328,2328,2328,2330,2334,2334,2350,2350,2351,2351,2351,2351,2352,2352,2352,2365,2366,2366,2366,2366,2368,2368,2368,2368,2371,2377,2377,2377,2382,2382,2382,2382,2383,2393,2393,2393,2395,2418,2418,2418,2419,2419,2420,2420,2421,2421,2421,2421,2422,2422,2422,2423,2425,2427,2427,2427,2428,2428,2428,2428,2431,2431,2431,2431,2432,2432,2432,2432,2436,2437,2437,2437,2438,2438,2438,2438,2439,2439,2446,2446,2447,2447,2450,2450,2452,2452,2452,2453,2454,2454,2454,2454,2455,2455,2455,2455,2464,2464,2464,2464,2466,2466,2466,2468,2469,2470,2470,2470,2471,2471,2471,2471,2472,2472,2473,2473,2475,2475,2475,2475,2476,2476,2476,2477,2478,2478,2478,2483,2488,2488,2488,2491,2515,2515,2515,2515,2516,2516,2516,2516,2533,2534,2534,2534,2535,2535,2535,2535,2537,2537,2538,2538,2539,2541,2541,2541,2542,2542,2542,2543,2544,2544,2544,2544,2546,2546,2546,2546,2549,2549,2549,2549,2550,2550,2550,2550,2551,2555,2557,2557,2571,2571,2571,2571,2572,2572,2573,2573,2574,2574,2574,2574,2575,2575,2581,2582,2586,2586,2586,2586,2587,2587,2587,2589,2592,2592,2592,2592,2593,2593,2593,2593,2595,2596,2596,2596,2597,2597,2597,2597,2598,2598,2599,2599,2600,2600,2600,2600,2610,2634,2634,2635,2636,2636,2636,2636,2637,2637,2637,2637,2640,2640,2640,2640,2642,2642,2642,2642,2653,2654,2654,2654,2655,2657,2657,2657,2658,2658,2662,2662,2666,2666,2666,2666,2667,2667,2667,2668,2669,2669,2669,2669,2670,2670,2670,2670,2676,2676,2693,2693,2694,2694,2694,2694,2695,2696,2696,2696,2697,2697,2697,2697,2699,2699,2700,2700,2701,2701,2701,2701,2702,2702,2702,2709,2710,2710,2710,2710,2712,2712,2712,2712,2715,2715,2715,2715,2716,2716,2716,2716,2717,2718,2718,2718,2722,2722,2722,2725,2750,2750,2751,2751,2752,2752,2752,2752,2753,2753,2753,2757,2759,2759,2759,2759,2760,2760,2760,2760,2763,2763,2763,2777,2778,2780,2780,2789,2791,2792,2792,2792,2793,2793,2793,2799,2800,2800,2801,2801,2802,2807,2807,2807,2809,2809,2809,2810,2817,2817,2819,2819,2820,2820,2820,2820,2823,2823,2823,2823,2831,2831,2831,2831,2832,2833,2833,2833,2834,2834,2834,2834,2835,2835,2836,2838,2840,2840,2840,2840,2841,2841,2841,2842,2843,2843,2843,2843,2844,2844,2844,2844,2862,2862,2862,2862,2863,2866,2866,2866,2871,2896,2896,2896,2897,2897,2897,2897,2899,2899,2900,2900,2901,2901,2901,2901,2902,2902,2902,2903,2904,2904,2904,2904,2908,2910,2910,2910,2913,2913,2913,2913,2914,2914,2914,2914,2915,2916,2916,2916,2918,2918,2918,2918,2919,2930,2940,2940,2941,2941,2943,2943,2944,2944,2944,2945,2947,2947,2947,2947,2948,2948,2953,2953,2956,2956,2956,2956,2957,2957,2957,2957,2959,2963,2963,2965,2966,2966,2966,2966,2967,2967,2968,2968,2969,2969,2969,2969,2973,2973,2973,2974,2975,2975,2975,2978,2979,2979,2979,2979,2994,2994,2994,2994,3020,3020,3020,3020,3021,3022,3022,3022,3023,3023,3023,3023,3024,3024,3025,3025,3027,3027,3027,3027,3028,3030,3030,3031,3032,3032,3032,3032,3033,3033,3033,3033,3039,3039,3057,3057,3058,3058,3058,3058,3065,3066,3066,3066,3067,3067,3069,3069,3073,3073,3077,3077,3078,3078,3078,3078,3079,3079,3079,3080,3081,3081,3081,3081,3083,3083,3083,3083,3086,3086,3086,3088,3089,3089,3089,3089,3090,3091,3091,3096,3098,3098,3098,3098,3099,3099,3100,3100,3101,3104,3104,3104,3105,3105,3105,3106,3116,3116,3116,3116,3117,3117,3117,3117,3120,3146,3146,3146,3147,3147,3147,3147,3155,3156,3156,3156,3157,3157,3157,3157,3158,3160,3161,3161,3162,3162,3162,3162,3164,3164,3164,3168,3169,3169,3169,3169,3170,3170,3173,3173,3176,3176,3176,3176,3178,3178,3180,3180,3181,3182,3182,3182,3183,3183,3183,3183,3184,3184,3185,3185,3187,3187,3187,3187,3188,3188,3188,3189,3190,3196,3196,3198,3199,3199,3199,3199,3211,3211,3211,3226,3227,3227,3227,3227,3246,3247,3255,3258,3259,3259,3259,3259,3261,3261,3262,3262,3267,3267,3267,3267,3278,3278,3278,3279,3280,3280,3280,3280,3282,3282,3282,3282,3309,3309,3309,3309,3310,3310,3310,3310,3311,3318,3318,3318,3320,3320,3320,3320,3321,3321,3322,3322,3323,3323,3323,3323,3330,3330,3330,3331,3335,3335,3335,3335,3336,3336,3338,3338,3341,3341,3341,3341,3342,3342,3342,3342,3344,3345,3345,3345,3346,3346,3346,3346,3347,3347,3348,3348,3349,3349,3349,3351,3353,3353,3353,3354,3355,3355,3355,3355,3356,3356,3356,3356,3359,3362,3362,3362,3364,3364,3364,3364,3365,3369,3369,3369,3374,3374,3374,3374,3375,3375,3376,3376,3380,3380,3380,3380,3381,3381,3381,3382,3383,3383,3383,3383,3384,3384,3384,3384,3390,3417,3417,3417,3418,3418,3418,3418,3419,3420,3420,3420,3421,3421,3424,3424,3426,3426,3445,3445,3446,3446,3446,3446,3447,3447,3449,3450,3451,3451,3451,3451,3453,3453,3453,3453,3456,3456,3456,3456,3457,3457,3457,3457,3458,3459,3459,3459,3475,3475,3475,3477,3478,3478,3482,3482,3483,3483,3483,3483,3484,3484,3484,3494,3496,3496,3496,3496,3497,3497,3497,3497,3500,3500,3500,3500,3505,3505,3505,3505,3507,3508,3508,3508,3509,3509,3509,3509,3510,3510,3511,3511,3512,3512,3512,3512,3514,3514,3514,3515,3516,3528,3528,3528,3529,3529,3529,3529,3532,3532,3532,3532,3560,3560,3560,3560,3561,3562,3562,3562,3563,3563,3568,3568,3569,3569,3576,3576,3578,3578,3578,3578,3579,3579,3579,3583,3584,3584,3584,3584,3585,3585,3585,3585,3591,3591,3591,3591,3592,3592,3603,3605,3606,3607,3607,3615,3616,3616,3616,3616,3618,3621,3622,3622,3623,3623,3623,3623,3624,3624,3624,3625,3626,3626,3626,3626,3646,3646,3646,3646,3649,3649,3649,3649,3650,3650,3650,3656,3657,3658,3658,3658,3660,3660,3660,3660,3661,3661,3662,3662,3663,3665,3665,3665,3666,3666,3666,3667,3669,3669,3672,3672,3673,3673,3673,3673,3682,3682,3682,3682,3683,3683,3683,3683,3685,3713,3715,3715,3716,3716,3716,3716,3717,3717,3718,3718,3719,3719,3719,3719,3723,3723,3723,3739,3740,3740,3740,3740,3741,3741,3741,3743,3746,3746,3746,3746,3748,3748,3748,3751,3752,3753,3753,3753,3754,3754,3754,3754,3755,3755,3756,3756,3758,3758,3758,3758,3763,3763,3763,3764,3765,3765,3765,3765,3766,3766,3766,3766,3772,3772,3772,3772,3773,3773,3773,3773,3774,3778,3778,3778,3779,3781,3781,3781,3789,3789,3790,3790,3797,3797,3797,3797,3798,3798,3798,3799,3800,3800,3800,3800,3802,3802,3802,3802,3805,3805,3807,3807,3808,3808,3808,3808,3809,3810,3810,3810,3812,3812,3832,3832,3861,3861,3862,3862,3863,3863,3863,3863,3864,3864,3864,3871,3873,3873,3873,3873,3886,3889,3889,3889,3892,3892,3892,3892,3903,3903,3903,3903,3907,3908,3908,3908,3909,3909,3909,3909,3914,3914,3918,3918,3919,3919,3919,3919,3921,3921,3921,3922,3923,3923,3923,3923,3924,3924,3924,3924,3927,3927,3927,3927,3929,3931,3931,3931,3932,3933,3936,3936,3937,3937,3937,3937,3938,3938,3939,3939,3941,3941,3941,3941,3942,3942,3942,3943,3944,3944,3946,3946,3947,3947,3947,3947,3959,3959,3959,3959,3960,3960,3960,3960,3961,3962,3962,3962,3979,3979,3979,3979,3981,3981,3982,3984,3985,3985,3985,3988,3989,4018,4018,4022,4023,4023,4023,4023,4025,4025,4025,4025,4028,4028,4028,4028,4029,4029,4029,4029,4034,4035,4035,4035,4037,4037,4037,4037,4038,4043,4044,4044,4045,4045,4045,4045,4046,4046,4046,4047,4051,4051,4051,4051,4052,4054,4054,4054,4075,4075,4075,4075,4076,4076,4076,4076,4078,4079,4079,4079,4080,4080,4080,4080,4081,4081,4082,4082,4083,4089,4091,4091,4093,4093,4093,4094,4095,4095,4095,4095,4096,4096,4096,4096,4105,4105,4105,4105,4107,4107,4107,4107,4108,4109,4109,4111,4112,4115,4115,4115,4116,4116,4117,4117,4125,4125,4125,4125,4126,4126,4126,4127,4128,4128,4128,4128,4129,4129,4129,4129,4159,4159,4159,4159,4160,4160,4160,4160,4161,4162,4171,4171,4172,4172,4172,4172,4174,4174,4175,4175,4176,4176,4176,4176,4177,4179,4182,4183,4184,4184,4189,4189,4191,4191,4191,4191,4194,4194,4194,4194,4195,4195,4195,4195,4196,4209,4209,4209,4213,4213,4215,4215,4216,4216,4217,4217,4218,4218,4218,4218,4219,4219,4219,4220,4222,4222,4222,4222,4223,4223,4223,4223,4226,4226,4226,4243,4244,4244,4244,4244,4246,4247,4247,4247,4248,4248,4248,4248,4249,4249,4250,4250,4251,4251,4251,4251,4253,4253,4274,4275,4280,4280,4280,4291,4292,4292,4292,4292,4295,4295,4295,4295,4299,4299,4299,4299,4300,4301,4307,4307,4308,4338,4338,4338,4345,4347,4351,4351,4353,4353,4353,4353,4354,4354,4354,4355,4356,4356,4356,4356,4357,4357,4357,4357,4363,4363,4363,4363,4364,4364,4376,4381,4382,4383,4383,4383,4384,4392,4392,4392,4394,4394,4395,4395,4396,4396,4396,4396,4397,4397,4397,4398,4399,4402,4402,4404,4408,4408,4408,4408,4411,4411,4411,4411,4412,4412,4412,4412,4413,4414,4414,4414,4416,4416,4416,4416,4417,4417,4418,4418,4423,4423,4423,4423,4424,4424,4424,4428,4430,4430,4430,4430,4431,4431,4431,4431,4434,4434,4434,4434,4435,4435,4438,4438,4440,4447,4447,4447,4448,4448,4448,4448,4449,4449,4450,4450,4451,4451,4451,4451,4459,4459,4459,4460,4491,4491,4491,4491,4492,4492,4494,4494,4497,4497,4497,4497,4499,4499,4499,4499,4500,4501,4501,4501,4502,4502,4502,4502,4503,4503,4504,4507,4529,4529,4529,4531,4532,4532,4532,4533,4534,4534,4534,4534,4535,4535,4535,4541,4559,4559,4559,4559,4560,4560,4560,4560,4561,4562,4562,4562,4567,4567,4567,4567,4571,4571,4572,4572,4573,4573,4573,4573,4574,4574,4574,4575,4576,4576,4576,4576,4590,4590,4590,4590,4593,4595,4595,4595,4596,4596,4596,4596,4597,4598,4598,4598,4600,4600,4600,4600,4601,4601,4602,4602,4603,4603,4603,4603,4604,4604,4606,4607,4609,4609,4609,4609,4610,4610,4610,4610,4613,4613,4613,4613,4614,4614,4614,4614,4618,4649,4649,4658,4659,4659,4659,4661,4662,4662,4663,4663,4664,4664,4664,4664,4666,4666,4666,4667,4668,4668,4668,4668,4669,4674,4674,4674,4677,4677,4677,4677,4687,4687,4687,4687,4688,4689,4689,4689,4690,4690,4690,4690,4691,4691,4692,4692,4694,4694,4697,4697,4698,4698,4698,4699,4700,4702,4702,4702,4703,4703,4703,4703,4715,4715,4715,4715,4716,4716,4716,4716,4717,4718,4718,4718,4719,4719,4727,4727,4729,4729,4751,4751,4752,4752,4752,4752,4765,4765,4765,4766,4767,4767,4767,4767,4769,4769,4769,4772,4775,4775,4775,4775,4776,4776,4776,4778,4779,4780,4780,4780,4782,4782,4782,4782,4783,4783,4784,4784,4785,4785,4785,4785,4786,4786,4786,4787,4819,4819,4819,4819,4824,4824,4824,4824,4827,4827,4827,4845,4846,4846,4846,4846,4848,4849,4854,4854,4861,4861,4861,4861,4862,4862,4863,4863,4864,4866,4866,4866,4868,4868,4868,4872,4873,4873,4873,4873,4874,4874,4874,4874,4877,4877,4877,4877,4879,4879,4879,4879,4880,4881,4883,4883,4884,4884,4884,4884,4885,4885,4886,4886,4890,4890,4890,4890,4891,4894,4894,4895,4896,4896,4896,4896,4897,4897,4897,4899,4905,4905,4905,4905,4906,4906,4906,4906,4907,4908,4908,4908,4909,4909,4909,4909,4911,4911,4912,4912,4913,4913,4913,4913,4918,4918,4918,4919,4920,4934,4934,4934,4936,4936,4936,4936,4945,4945,4948,4948,4949,4949,4949,4949,4950,4951,4951,4951,4955,4987,4987,4987,4988,4988,4989,4989,5012,5012,5012,5017,5018,5018,5018,5019,5021,5021,5021,5021,5022,5022,5022,5022,5025,5025,5027,5027,5028,5028,5028,5028,5030,5031,5031,5031,5032,5032,5032,5035,5036,5036,5037,5037,5038,5038,5038,5038,5040,5040,5040,5047,5048,5048,5048,5048,5049,5049,5049,5049,5052,5052,5052,5052,5056,5056,5056,5056,5057,5061,5061,5061,5062,5062,5062,5062,5067,5067,5068,5068,5070,5070,5070,5070,5071,5071,5071,5072,5079,5079,5079,5079,5080,5080,5080,5080,5086,5086,5086,5086,5087,5089,5089,5089,5090,5091,5091,5091,5110,5110,5110,5118,5120,5120,5121,5121,5122,5122,5122,5122,5123,5123,5123,5124,5125,5125,5127,5127,5135,5135,5135,5135,5168,5168,5168,5168,5169,5172,5172,5172,5173,5174,5174,5174,5176,5176,5176,5176,5177,5177,5190,5202,5203,5203,5203,5203,5204,5204,5204,5205,5207,5207,5207,5207,5208,5208,5208,5208,5211,5211,5217,5217,5218,5218,5218,5218,5228,5229,5229,5229,5230,5230,5230,5230,5231,5231,5241,5241,5242,5242,5242,5242,5246,5246,5269,5270,5271,5271,5271,5271,5272,5274,5274,5274,5277,5277,5277,5277,5279,5279,5279,5279,5280,5281,5281,5281,5282,5282,5282,5282,5283,5283,5284,5284,5286,5286,5288,5288,5289,5289,5289,5293,5294,5294,5294,5297,5298,5298,5298,5298,5304,5304,5304,5304,5305,5305,5305,5305,5306,5307,5307,5309,5310,5315,5315,5315,5319,5319,5320,5320,5321,5321,5321,5321,5322,5355,5355,5356,5357,5357,5357,5357,5359,5359,5359,5359,5374,5374,5374,5374,5375,5375,5375,5375,5382,5383,5383,5383,5385,5385,5385,5385,5386,5386,5387,5387,5388,5388,5388,5388,5389,5391,5391,5392,5394,5394,5394,5394,5395,5395,5395,5395,5404,5404,5404,5404,5405,5405,5405,5405,5409,5410,5410,5410,5411,5411,5413,5413,5414,5414,5415,5415,5416,5419,5419,5419,5421,5421,5421,5440,5441,5441,5441,5441,5442,5442,5442,5442,5445,5445,5445,5447,5449,5449,5449,5449,5450,5451,5451,5451,5452,5452,5452,5452,5453,5453,5454,5454,5456,5456,5456,5456,5457,5457,5462,5463,5468,5468,5468,5468,5469,5469,5472,5472,5496,5496,5496,5496,5497,5497,5497,5497,5498,5502,5502,5502,5503,5503,5503,5503,5537,5539,5540,5540,5541,5541,5541,5541,5542,5542,5542,5543,5544,5544,5544,5544,5546,5546,5546,5546,5549,5549,5549,5549,5550,5550,5552,5552,5553,5554,5554,5557,5559,5559,5559,5559,5560,5560,5561,5561,5562,5562,5562,5562,5563,5563,5563,5564,5568,5568,5568,5570,5571,5571,5571,5571,5574,5574,5574,5574,5575,5575,5575,5575,5577,5578,5578,5578,5579,5588,5588,5588,5589,5589,5593,5593,5598,5598,5598,5598,5612,5612,5612,5613,5614,5614,5614,5614,5615,5615,5615,5615,5618,5618,5618,5623,5625,5625,5625,5625,5626,5633,5633,5633,5634,5634,5634,5634,5647,5647,5648,5648,5652,5652,5652,5652,5653,5653,5653,5654,5655,5655,5655,5655,5656,5656,5658,5658,5664,5667,5667,5667,5668,5668,5668,5668,5669,5703,5703,5703,5704,5704,5704,5704,5706,5706,5707,5707,5708,5708,5708,5710,5711,5711,5711,5715,5716,5716,5716,5716,5718,5718,5718,5718,5721,5721,5721,5721,5722,5722,5722,5722,5723,5724,5724,5724,5744,5744,5768,5768,5769,5784,5785,5785,5786,5786,5786,5786,5787,5787,5787,5788,5790,5790,5790,5790,5791,5791,5791,5791,5794,5796,5796,5796,5797,5797,5797,5797,5799,5800,5800,5800,5801,5801,5801,5801,5812,5812,5813,5813,5814,5814,5814,5814,5816,5816,5818,5828,5829,5829,5829,5829,5830,5830,5830,5830,5839,5839,5839,5839,5847,5847,5847,5847,5848,5849,5849,5849,5850,5850,5850,5852,5853,5853,5854,5854,5856,5856,5856,5856,5857,5857,5857,5858,5859,5859,5859,5859,5860,5860,5860,5860,5866,5866,5866,5866,5901,5907,5907,5907,5908,5909,5909,5909,5910,5910,5910,5910,5912,5920,5921,5921,5922,5922,5922,5922,5923,5923,5923,5924,5925,5927,5927,5927,5931,5931,5931,5931,5934,5934,5934,5934,5935,5935,5935,5935,5936,5940,5940,5940,5942,5942,5942,5942,5943,5946,5953,5953,5954,5954,5954,5954,5955,5955,5955,5956,5958,5963,5963,5963,5964,5964,5964,5964,5967,5967,5967,5967,5968,5968,5968,5970,5972,5973,5973,5973,5974,5974,5974,5974,5975,5975,5976,5976,5977,5977,5977,5977,5981,5981,5981,5982,5983,5983,5986,5986,6011}; int main() { int T; T = read(); while(T--) { int n; n = read(); printf("%d\n",db[n - 1]); } }