Unlocker.ino

/*
 *  DSC Unlocker 1.3 (esp8266)
 *
 *  Checks all possible 4-digit installer codes until a valid code is found, including handling keypad
 *  lockout if enabled.  The valid code is output to serial as well as repeatedly flashed with the
 *  built-in LED - each digit is indicated by the number of blinks, a long blink indicates "0".  This
 *  esp8266 example tests codes in order of most commonly used general 4-digit codes:
 *  https://www.datagenetics.com/blog/september32012/
 *
 *  If keypad lockout has been enabled by the installer, the sketch waits for the lockout to expire
 *  before continuing the code search.  The physical keypads may beep when this occurs, the keypads can
 *  be disconnected for silence during the code search.
 *
 *    - Keypad lockout can be skipped if a valid access code to arm/disarm the panel is entered in
 *      the sketch settings.  The sketch will trigger an arm/disarm cycle before the keypad
 *      lockout - this will result in beeps from the physical keypads each arm/disarm cycle.
 *
 *    - If a valid access code is not available and the current configuration on the panel is not
 *      needed, the keypad lockout can also be skipped by using a relay to automatically power cycle
 *      the panel while the panel is set to factory default (on the PC1864, by connecting a jumper
 *      wire from PGM1 to Z1). This has been tested with the commonly available relay boards using
 *      the Songle SRD-05VDC-SL-C relay (~1USD shipped).
 *
 *    - The Wemos Relay Shield v1 is hardwired to connect using the D1 pin and will conflict with this
 *      interface if using the default wiring scheme and plugging directly into the Wemos D1 mini. Wire
 *      the relay board separately (without plugging in directly to the Wemos board) to connect the relay
 *      board D1 pin to a different esp8266 pin (or use a different relay board).
 *
 *  Example maximum unlocking times on the PC1864:
 *    - Without keypad lockout: ~8h20m
 *    - With 6 attempt/5 minute keypad lockout: ~6d3h13m
 *    - With 6 attempt keypad lockout and skipping via arm/disarm reset: ~10hr18m
 *    - With 6 attempt keypad lockout and skipping via relay reset: ~19h27m
 *
 *  Note that if the panel was configured remotely (using the panel communicator), it is possible for the
 *  installer to lock out local programming - if so, this sketch will not be able to determine the code.
 *
 *  This example sketch also demonstrates how to check the panel status for states that are not tracked in
 *  the library using dsc.status[partition] (as seen in dscKeybusPrintData.cpp-printPanelMessages())
 *  and how check for specific panel commands using dsc.panelData[] (as seen in
 *  dscKeybusPrintData.cpp-printPanelMessage()).
 *
 *  Usage:
 *    - Run the sketch while the security system does not need to be armed - keypads will be unavailable
 *      during the search.
 *    - Press any key via serial to pause and resume the code search.
 *    - If the sketch is restarted, the code search can be resumed at the last known position by setting
 *      `startPosition`.
 *
 *  Release notes:
 *    1.3 - Add skipping keypad lockout by arm/disarm cycle with a valid access code
 *    1.2 - Check for valid panel state at startup
 *    1.1 - Updated esp8266 wiring diagram for 33k/10k resistors
 *    1.0 - Initial release
 *
 *  Wiring:
 *      DSC Aux(+) --- 5v voltage regulator --- esp8266 development board 5v pin (NodeMCU, Wemos)
 *
 *      Alternatively if using a relay, external power is required instead of using DSC Aux(+):
 *      External USB or 5v DC power supply --- esp8266 development board USB or 5v pin (NodeMCU, Wemos)
 *
 *      DSC Aux(-) --- esp8266 Ground
 *
 *                                         +--- dscClockPin (esp8266: D1, D2, D8)
 *      DSC Yellow --- 33k ohm resistor ---|
 *                                         +--- 10k ohm resistor --- Ground
 *
 *                                         +--- dscReadPin (esp8266: D1, D2, D8)
 *      DSC Green ---- 33k ohm resistor ---|
 *                                         +--- 10k ohm resistor --- Ground
 *
 *      Virtual keypad:
 *      DSC Green ---- NPN collector --\
 *                                      |-- NPN base --- 1k ohm resistor --- dscWritePin (esp8266: D1, D2, D8)
 *            Ground --- NPN emitter --/
 *
 *  Virtual keypad uses an NPN transistor to pull the data line low - most small signal NPN transistors should
 *  be suitable, for example:
 *   -- 2N3904
 *   -- BC547, BC548, BC549
 *
 *  Relay (Songle SRD-05VDC-SL-C based board) - optional to skip keypad lockout:
 *          DSC power adapter (one wire) --- DSC AC
 *          DSC power adapter (one wire) --- Relay board COM (common)
 *      Relay board NC (normally closed) --- DSC AC
 *            Relay board trigger signal --- dscRelayPin (esp8266: D5, D6, D7)
 *                        Relay board 5v --- esp8266 development board 5v pin (NodeMCU, Wemos)
 *                       Relay board GND --- Ground
 *
 *  Issues and (especially) pull requests are welcome:
 *  https://github.com/taligentx/dscKeybusInterface
 *
 *  This example code is in the public domain.
 */

#include <dscKeybusInterface.h>

// Settings
const char* accessCode = "";    // Optional, skips keypad lockout if enabled by arming/disarming the panel
const int   startPosition = 0;  // Starting test position, set if the process is interrupted

// Configures the Keybus interface with the specified pins
#define dscClockPin D1  // esp8266: D1, D2, D8 (GPIO 5, 4, 15)
#define dscReadPin  D2  // esp8266: D1, D2, D8 (GPIO 5, 4, 15)
#define dscWritePin D8  // esp8266: D1, D2, D8 (GPIO 5, 4, 15)
#define dscRelayPin D6  // esp8266: D5, D6, D7 (GPIO 14, 12, 13) - Optional, leave this pin disconnected if not using a relay

// Commonly known DSC codes are tested first
const int codeList[] = {
1000,1182,1212,1234,1500,1550,1555,1626,1676,1984,2500,2525,2530,3000,3101,4010,4020,4112,5010,5020,5050,5150,5555,6321,
6900,9010,1111,0,7777,1004,2000,4444,2222,6969,9999,3333,6666,1122,1313,8888,2001,4321,1010,909,2580,7,1818,1230,1986,70,
1985,987,1231,1987,1999,2468,2002,2323,123,1123,1233,1357,1221,1324,1988,2112,2121,1024,1112,1224,1969,1225,1235,1982,
1983,1001,1978,1979,7410,1020,1223,1974,1975,1977,1980,1981,1029,1121,1213,1973,1976,2020,2345,2424,1515,1970,1972,
1989,1,1023,1414,9876,101,907,1245,1966,1967,1971,8520,1964,1968,4545,1318,5678,1011,1124,1211,1963,4200,4567,1007,1012,1025,
1120,1125,1214,1236,1965,7942,1028,1209,1227,3535,7890,420,1210,1222,1701,1919,5425,1113,1226,1717,1957,1959,1990,5252,202,1002,
1003,1114,1205,1215,1220,1228,1956,1962,3232,124,303,505,815,1013,1014,1021,1022,1027,1030,1101,1128,1133,1945,1955,1960,3030,
3210,9090,77,1092,1126,1130,1204,1005,1009,1031,1104,1115,1117,1119,1127,1203,1217,1218,1379,1958,3434,5656,7878,411,1017,
1018,1019,1026,1103,1129,1216,1229,1961,1991,2626,6789,8282,9111,321,808,1008,1015,1102,1118,1201,1202,1232,2727,3456,7979,102,
707,1052,1105,1206,1207,1208,1616,1953,1954,1998,2848,3131,121,147,316,1006,1219,1243,1942,2003,5000,5454,11,125,404,912,
1107,1108,1314,1423,1951,1952,2004,2211,2233,2828,214,1016,1100,1106,1110,1116,1478,1950,1992,3636,4242,8989,203,604,911,
1109,1254,1321,1492,1949,7788,120,311,1256,1290,1346,4141,9,210,314,922,1369,1432,1472,2486,4862,83,213,510,625,1200,
1453,1947,1948,110,204,313,326,412,711,722,908,923,1066,1323,1331,1776,2510,3117,4040,7894,9981,24,512,515,918,927,
928,1312,1415,2010,2244,2929,5151,5683,6996,7070,7272,7474,12,111,128,220,225,302,310,315,318,323,402,410,413,416,
423,428,502,525,606,714,811,822,917,924,1080,1134,1188,1411,1412,1812,1907,1941,1944,1946,1993,1994,1996,1997,2005,2008,
2103,2356,5858,6464,6669,8080,112,122,304,305,312,325,327,611,704,712,809,829,1248,1437,1940,1943,1995,2123,2210,2212,
2332,2412,3211,3214,3838,4001,4646,4747,9898,9988,13,69,99,103,114,209,212,258,301,319,331,405,408,419,501,509,
513,517,521,523,622,721,813,818,913,914,926,929,1144,1311,1590,1911,1937,2469,3579,4711,4860,5757,5888,116,205,208,
217,228,317,330,414,415,417,486,507,524,610,612,613,624,666,807,812,820,915,919,1199,1345,1452,1800,1914,2110,
2311,2501,3690,3737,3939,4000,4455,4848,7575,7913,104,119,127,129,130,218,219,221,224,322,328,425,426,526,616,708,
710,825,904,916,921,925,1177,1350,1404,1809,1928,1939,2111,2202,2312,2314,2341,3006,6767,78,117,118,206,211,215,223,
324,407,424,504,506,516,522,614,723,728,729,810,824,828,920,1155,2006,2104,2226,2255,4343,5588,6565,7896,8585,9000,
105,126,131,222,306,307,320,418,427,429,511,527,607,617,701,717,724,725,727,802,804,823,906,1258,1300,1342,
1397,1470,1905,2011,3322,3344,3355,3412,5959,8787,10,98,108,113,227,242,308,514,518,520,601,615,805,816,901,910,
930,1244,1322,1325,1410,1425,1469,1730,1793,1908,2122,2131,2310,2918,3113,3133,3223,3515,4123,4568,4949,5353,5566,6262,8426,
8899,9874,71,79,107,109,115,201,216,406,421,422,519,602,623,709,826,1237,1250,1269,1310,1358,1441,1456,1466,1516,
1525,1933,1938,2012,2100,2134,2205,2258,2357,3256,3321,3477,4004,6405,7899,8484,9696,2,226,309,329,401,403,528,530,531,
618,620,628,713,719,831,852,1255,1329,1380,1402,1435,1821,1920,2007,2324,2333,2511,3112,3377,3669,3927,4562,5525,6363,6868,
7000,7007,7676,7734,8181,9292,9900,8,529,603,609,621,626,702,715,718,803,814,817,903,1305,1333,1511,1512,1596,
1711,1881,1900,1925,2223,2369,2411,2425,2442,3013,3111,3141,3353,7412,80,106,190,207,409,503,508,619,703,705,731,801,
827,1070,1132,1138,1192,1301,1309,1315,1420,1541,1710,1789,1888,1903,2101,2105,2133,2234,2236,2288,2401,3310,4561,5001,6497,
6699,430,605,720,806,821,902,905,1042,1238,1240,1302,1303,1304,1317,1320,1407,1471,1510,1518,1523,1542,1598,1936,2301,2304,
2410,2512,2514,3213,3216,3323,3421,3825,4111,4865,5129,5225,5432,5665,7171,7373,7711,7749,8008,9191,9510,187,608,629,706,726,
819,1088,1239,1278,1289,1307,1316,1359,1532,1623,1688,1707,1820,1836,1892,1902,1917,1929,1932,2021,2204,2213,2230,2235,2313,2456,
2588,3001,3003,3110,3123,3215,3233,3311,4114,4201,4268,4556,5123,5646,6609,7531,8000,8686,9115,9911,23,627,630,716,1098,1145,
1147,1187,1241,1288,1326,1340,1356,1408,1477,1501,1504,1505,1520,1524,1530,1595,1718,1775,1810,1904,1909,1910,1912,2013,2124,
2143,2232,2277,2303,2306,2321,2508,2513,2526,2527,3021,3160,3231,3388,3452,3800,4456,4488,4554,4563,4989,6543,7789,7895,8246,9119,
143,830,1032,1040,1135,1166,1175,1178,1308,1332,1347,1401,1403,1430,1458,1479,1502,1503,1602,1608,1610,1803,1819,1877,1906,1935,
2009,2107,2109,2126,2132,2200,2201,2208,2215,2218,2322,2326,2334,2413,2505,2611,2707,2712,2811,3122,3212,3366,4416,4500,4565,5112,
5577,5654,6060,6942,7799,9595,9632,21,22,152,979,1041,1069,1131,1141,1284,1319,1375,1416,1417,1424,1488,1551,1603,1604,1618,
1652,1664,1665,1719,1927,2015,2030,2080,2120,2130,2203,2307,2308,2327,2507,2610,2662,2684,2911,3011,3108,3369,4232,4244,6161,6357,
7654,7787,8021,3,369,1090,1140,1149,1172,1185,1247,1253,1280,1334,1378,1406,1409,1413,1418,1421,1422,1434,1611,1709,1712,1728,
1732,1828,1901,1918,1922,1923,1930,2022,2023,2094,2102,2108,2114,2207,2221,2302,2316,2405,2503,2552,2612,2711,2903,3004,3105,3125,
3221,3334,4011,4474,4477,4486,4512,4884,5013,7411,7856,8411,8765,9797,351,730,999,1033,1035,1036,1038,1143,1162,1242,1286,
1306,1328,1400,1405,1428,1431,1444,1486,1508,1540,1545,1589,1597,1599,1612,1624,1703,1804,1811,1924,1934,2025,2106,2115,2136,2225,
2229,2231,2300,2305,2309,2318,2325,2331,2404,2406,2417,2504,2520,2589,2710,3121,3250,3303,3320,3325,3658,3721,4433,4523,5115,5233,
5456,5544,5881,7117,7123,7778,9413,9583,9630,72,584,1037,1067,1174,1198,1257,1277,1299,1433,1436,1507,1517,1521,1580,1617,1705,
1771,1807,1808,1879,1913,2040,2046,2050,2113,2119,2144,2206,2214,2272,2337,2365,2402,2407,2464,2502,2575,2606,2633,2802,3010,3012,
3055,3103,3132,3234,3245,3312,3313,3433,3435,3511,3691,3698,4007,4142,4288,4431,4564,4569,4578,5212,5354,5424,5677,5689,6667,7179,
7399,7458,7477,8808,8898,9009,9110,9991,4,14,342,357,691,990,1057,1064,1079,1139,1152,1154,1156,1169,1327,1352,1438,1440,
1506,1509,1526,1559,1567,1605,1620,1700,1704,1713,1725,1778,1801,1805,1822,2024,2125,2150,2187,2209,2241,2266,2358,2408,2415,
2430,2441,2509,2539,2609,2622,2703,2728,2772,2810,2910,3134,3236,3304,3570,3651,3840,4333,4422,4560,4600,4700,5070,5412,5522,5788,
5882,6688,6761,6977,7771,8462,8509,9773,9989,5,20,25,90,100,159,230,333,1047,1050,1058,1083,1151,1180,1252,1266,1298,
1372,1377,1457,1475,1476,1514,1522,1552,1570,1575,1601,1628,1702,1777,1788,1860,1899,1921,2026,2117,2135,2290,2315,2367,2400,2403,
2422,2434,2435,2455,2466,2506,2603,2627,2708,2801,2812,2882,2925,3007,3157,3166,3200,3235,3254,3266,3270,3324,3339,3399,3403,3512,
3693,3699,3802,4219,4312,4411,4445,4566,4654,5200,5221,5246,5263,5423,5455,5623,5674,5880,5912,6125,6453,6540,6677,7103,7779,8383,
9877,18,27,33,777,880,1055,1056,1074,1077,1148,1153,1167,1168,1173,1191,1246,1249,1330,1337,1429,1450,1451,1531,1600,1621,
1632,1666,1721,1722,1739,1870,1876,1887,1926,2045,2141,2169,2217,2224,2228,2242,2243,2245,2252,2257,2342,2344,2378,2423,2426,2428,
2480,2482,2522,2574,2579,2604,2705,2777,2808,2846,3025,3100,3107,3124,3224,3315,3318,3411,3577,3663,4144,4421,4466,4520,4864,4868,
5004,5005,5105,5420,5421,5533,5574,5844,5861,5963,6988,7001,7301,7889,8013,8575,8624,9087,9112,9947,188,456,900,1137,1150,1159,
1260,1263,1276,1279,1297,1349,1385,1442,1443,1578,1579,1609,1622,1699,1706,1708,1802,1806,1814,1824,1832,1915,2014,2145,2237,2280,
2336,2389,2409,2519,2531,2569,2689,2704,2709,2714,2804,2806,2905,3120,3179,3283,3300,3331,3332,3522,3618,3733,4130,4231,
4354,4441,4555,4785,5153,5333,5375,5511,5763,6000,6017,6822,7011,7077,7200,7414,7643,7707,7712,7773,7869,7887,7988,7997,8011,8070,
8088,8210,8311,8472,8586,8588,8779,8951,9022,9494,9933,9942,9966,9990,6,15,17,64,88,134,189,250,690,800,878,879,
982,1046,1048,1053,1065,1071,1072,1073,1157,1163,1265,1268,1275,1285,1335,1351,1364,1382,1386,1388,1399,1427,1528,1538,1569,1583,
1592,1654,1720,1727,1774,1781,1823,1827,1931,2118,2140,2180,2269,2319,2330,2414,2416,2429,2431,2467,2477,2488,2523,2529,2607,2706,
2909,3126,3158,3201,3217,3277,3357,3363,3578,3790,4150,4415,4582,4620,4815,5168,5325,5410,5417,5523,6200,6225,7202,7277,7304,
7610,7865,8010,8107,8504,8577,8642,8877,9001,9012,9711,9870,145,479,555,1063,1068,1094,1171,1179,1184,1186,1190,1251,1267,1272,
1273,1274,1336,1338,1344,1348,1355,1365,1446,1513,1533,1534,1535,1537,1548,1606,1607,1690,1726,1754,1825,1830,1840,1850,1890,
2019,2142,2148,2164,2216,2219,2335,2346,2355,2448,2515,2587,2600,2628,2701,2723,2816,2855,2912,3009,3114,3142,3316,3326,3341,3410,
3424,3443,3451,3534,3537,3727,4077,4125,4224,4258,4414,4454,4521,4546,4588,4589,4663,4666,4682,4790,5011,5121,5169,5193,5210,5254,
5362,5433,5500,5503,6288,6542,6661,7100,7210,7227,7256,7700,7744,7755,7769,7879,7882,8108,8264,8424,8998,9312,9512,9669,9801,
9878,9899,9955,74,789,1043,1051,1075,1087,1142,1259,1262,1264,1283,1339,1370,1447,1454,1459,1544,1591,1593,1634,1678,1714,1723,
1790,1829,1852,1883,1916,2027,2116,2220,2263,2274,2279,2286,2328,2340,2366,2391,2436,2516,2528,2541,2555,2563,2590,2601,2605,2608,
2625,2809,2829,2907,2935,2987,3002,3033,3130,3144,3198,3203,3267,3299,3330,3337,3345,3367,3425,3500,3504,3553,3569,3637,3792,3947,
4121,4402,4404,4448,4543,4587,5104,5155,5177,5211,5232,5236,5253,5404,5488,5575,5687,5885,6112,6636,6644,6660,6783,6869,7102,7491,
7557,7718,7766,7897,7911,7987,7999,8272,8312,8521,8525,8824,8889,9014,9225,9394,9713,32,140,158,577,933,972,1181,1197,1295,
1296,1341,1343,1353,1354,1374,1391,1394,1419,1448,1467,1489,1490,1519,1627,1733,1735,1815,1844,1875,1882,1889,2016,2017,2028,2052,
2063,2177,2317,2343,2362,2385,2390,2427,2479,2481,2521,2719,2881,2930,3008,3090,3104,3135,3164,3206,3278,3280,3287,3314,3528,3536,
3654,3981,4211,4213,4214,4332,4400,4417,4570,4575,4653,4656,4769,4774,4778,4866,5160,5213,5223,5270,5308,5366,5400,5477,5486,5556,
5565,5625,5746,5825,5967,5978,6465,6544,6655,6786,7111,7198,7448,7577,7644,7667,7774,7904,7958,8001,8018,8252,8425,8649,8650,8669,
8789,8848,8875,9513,9998,16,45,49,75,243,550,588,770,985,1054,1076,1086,1089,1161,1176,1270,1361,1366,1368,1371,1381,
1387,1426,1455,1463,1468,1543,1562,1563,1568,1661,1684,1729,1744,1783,1893,1898,2099,2127,2128,2129,2138,2147,2154,2157,2192,2227,
2240,2265,2320,2338,2354,2418,2420,2421,2432,2433,2470,2533,2534,2545,2546,2550,2576,2583,2613,2653,2666,2722,2733,2803,2805,2807,
2864,2901,2904,3014,3119,3129,3169,3184,3220,3241,3246,3288,3294,3301,3474,3521,3600,3707,3711,3811,3849,4100,4122,4210,4420,
4425,4442,4484,4647,5152,5154,5202,5222,5245,5248,5250,5251,5255,5257,5321,5445,5458,5494,5545,5546,5548,5600,5673,5693,5846,
5957,6123,6525,6541,6665,6785,6797,6874,6895,6987,7004,7023,7150,7456,7704,7717,7733,7891,7898,8118,8153,8158,8186,8511,8884,8912,
8919,9080,9393,9779,9889,9979,9995,19,229,1034,1044,1095,1099,1158,1170,1189,1281,1363,1390,1480,1484,1527,1536,1564,1619,1680,
1724,1740,1835,1869,1880,1897,2018,2067,2170,2181,2251,2275,2276,2287,2298,2360,2377,2399,2419,2450,2458,2517,2518,2524,2548,2554,
2568,2585,2602,2620,2624,2639,2663,2729,2868,2906,3005,3015,3115,3118,3168,3225,3237,3305,3356,3373,3436,3542,3652,4021,4202,
4234,4365,4381,4424,4460,4511,4532,4533,4742,4775,4789,5060,5120,5280,5306,5315,5464,5478,5512,5567,5621,5711,5789,5946,5960,6411,
6449,6592,6653,6685,6712,6769,6978,7002,7110,7245,7475,7486,7511,7677,7714,7722,7829,7852,7873,7877,7931,8421,8461,8502,8814,8910,
8988,9023,9200,9339,9485,9731,9865,9875,9987,41,42,76,89,138,144,153,157,345,431,1045,1078,1081,1082,1096,1160,1193,
1282,1571,1613,1636,1637,1669,1670,1686,1885,1886,2033,2137,2160,2185,2188,2248,2285,2351,2375,2379,2452,2462,2465,2474,2535,2536,
2565,2582,2615,2755,2767,2779,2813,2819,2834,2839,2888,2908,2972,2999,3024,3031,3145,3159,3227,3261,3281,3309,3328,3335,3336,3338,
3426,3432,3478,3541,3547,3556,3666,3692,3710,3777,3824,4017,4024,4157,4160,4212,4245,4325,4356,4412,4601,4812,4817,4855,4869,5051,
5335,5465,5528,5585,5599,5612,5628,5657,5698,5713,5715,6155,6316,6353,6486,6776,6778,6842,6886,6963,7101,7172,7211,7447,7500,7576,
7611,7757,7861,7867,7959,8100,8126,8184,8310,8456,8489,8523,8678,8759,8800,8850,8864,8900,8901,9006,9117,9123,9677,9799,9813,9856,
9871,9916,9977,9996,66,137,142,166,192,282,442,778,1060,1084,1091,1136,1146,1164,1165,1183,1194,1271,1362,1389,1461,1485,
1487,1546,1547,1553,1560,1577,1586,1588,1594,1614,1615,1625,1644,1668,1692,1745,1750,1760,1770,1773,1787,1813,1826,1845,1848,2029,
2031,2044,2055,2060,2085,2153,2239,2246,2250,2278,2282,2284,2299,2329,2347,2368,2439,2451,2457,2460,2475,2478,2566,2614,2700,
2789,2800,3109,3128,3161,3208,3209,3219,3222,3240,3258,3380,3406,3444,3467,3486,3513,3545,3585,3612,3613,3615,3625,3672,3818,3823,
3894,3914,3918,4033,4041,4055,4126,4127,4128,4206,4235,4243,4256,4539,4548,4628,4649,4657,4722,4901,5024,5028,5116,5117,5133,5242,
5310,5312,5504,5521,5535,5551,5554,5754,5808,5809,5841,5869,5966,6164,6275,6325,6369,6461,6554,6559,6633,6664,6713,7095,7260,7306,
7321,7326,7337,7579,7604,7678,7824,7845,7902,7909,7989,8055,8133,8207,8318,8350,8477,8487,8811,8828,9125,9969,31,200,235,663,
734,864,980,988,1049,1261,1287,1367,1398,1474,1481,1482,1573,1574,1587,1629,1631,1638,1648,1663,1736,1834,1838,1862,1864,2032,
2034,2047,2088,2090,2155,2156,2199,2238,2262,2294,2348,2350,2443,2461,2532,2570,2621,2652,2667,2669,2686,2688,2702,2715,2718,2818,
2856,3020,3116,3155,3182,3204,3242,3244,3251,3259,3286,3291,3306,3386,3415,3430,3445,3455,3462,3476,3510,3543,3594,3639,3810,3841,
3911,4012,4013,4022,4050,4152,4221,4225,4313,4550,4586,4655,4710,4800,4879,4967,5052,5055,5111,5124,5230,5282,5330,5386,5411,5438,
5463,5466,5514,5563,5564,5595,5735,5758,5791,5879,5969,6036,6109,6110,6111,6210,6211,6251,6280,6455,6500,6556,6566,6611,6656,6676,
6697,6912,6970,6989,7022,7151,7177,7188,7418,7421,7512,7532,7612,7765,7770,7776,7780,7782,7860,7892,7982,8007,8180,8203,8228,8500,
8512,8513,8612,8675,8721,8788,8812,8925,8972,8977,9091,9100,9201,9815,9909,55,60,168,684,741,1291,1293,1554,1566,1585,
1643,1675,1682,1715,1785,1816,1817,1841,1861,1874,1884,2139,2149,2162,2165,2174,2179,2253,2254,2256,2268,2349,2353,2380,2444,2454,
2472,2483,2547,2578,2586,2665,2668,2773,2815,2820,2823,2825,2837,3017,3042,3102,3150,3199,3253,3327,3343,3414,3422,3423,3533,3791,
3900,4042,4044,4102,4124,4133,4179,4185,4228,4248,4255,4311,4329,4334,4418,4446,4469,4497,4501,4516,4535,4544,4547,4591,4680,4861,
4867,4932,4994,5021,5025,5126,5162,5165,5234,5291,5304,5337,5355,5377,5451,5510,5513,5543,5557,5586,5645,5777,6126,6206,6249,6266,
6310,6399,6425,6548,6570,6663,6668,6687,6694,6801,6911,6954,6968,7018,7021,7332,7374,7377,7415,7466,7478,7602,7603,7726,7747,7759,
7880,7946,7980,8002,8104,8119,8123,8258,8384,8572,8668,8711,8723,8822,8855,8890,8892,8991,9852,9919,35,44,73,179,191,343,
346,385,535,571,1059,1195,1292,1360,1383,1384,1445,1561,1565,1572,1635,1641,1671,1674,1677,1679,1691,1716,1731,1734,1747,1786,
1842,1865,1871,2035,2057,2064,2065,2146,2151,2161,2168,2175,2178,2247,2374,2485,2497,2543,2567,2577,2617,2648,2657,2713,2814,2817,
2833,2873,2900,2902,3040,3152,3163,3180,3218,3243,3247,3255,3265,3317,3352,3358,3379,3400,3420,3453,3505,3546,3588,3611,3614,3703,
3750,3814,3925,3942,3945,3971,4015,4078,4110,4113,4115,4176,4320,4322,4344,4383,4386,4440,4513,4536,4540,4611,4725,5007,5022,5100,
5110,5156,5157,5235,5262,5268,5284,5348,5413,5415,5440,5461,5507,5578,5579,5603,5624,5635,5639,5669,5775,5781,5800,5852,6006,6120,
6154,6165,6254,6300,6364,6366,6407,6412,6488,6511,6545,6622,6662,6768,6890,6972,7080,7090,7137,7142,7189,7250,7313,7533,7580,7673,
7721,7727,7775,7812,7912,7920,7981,8081,8090,8111,8112,8234,8589,8798,8809,8810,8893,9008,9011,9333,9515,9606,9744,9753,9812,9821,
9939,26,28,29,63,82,92,337,532,942,977,978,989,1085,1093,1196,1376,1395,1460,1473,1584,1633,1642,1647,1649,1657,
1687,1772,1849,1894,1896,2049,2056,2070,2077,2196,2281,2291,2364,2370,2437,2447,2453,2473,2489,2551,2561,2623,2635,2650,2677,2717,
2720,2721,2725,2750,2853,2916,2922,3032,3035,3060,3070,3080,3089,3106,3147,3162,3202,3207,3279,3298,3302,3375,3442,3457,3472,3501,
3519,3524,3575,3580,3587,3590,3622,3624,3628,3879,3883,3960,4161,4168,4171,4223,4274,4279,4372,4450,4489,4664,5002,5017,5032,5102,
5103,5144,5191,5231,5256,5418,5419,5441,5472,5560,5576,5593,5602,5610,5632,5633,5812,5940,6023,6064,6157,6245,6336,6372,6420,6610,
6626,6638,6654,6658,6775,6795,6920,6971,6999,7068,7112,7116,7162,7235,7274,7391,7535,7605,7664,7737,7758,7786,7807,7811,7854,8113,
8301,8432,8448,8468,8486,8542,8648,8702,8778,8869,8881,8920,9015,9173,9311,9498,9500,9519,9551,9555,9633,9725,9788,9789,9912,9951,
68,87,180,199,248,344,485,689,775,890,945,1061,1062,1396,1465,1529,1556,1645,1683,1689,1743,1780,1784,1833,1837,1855,
1856,1863,1873,1878,2048,2093,2163,2166,2273,2297,2359,2388,2395,2484,2487,2491,2542,2631,2636,2658,2679,2737,2781,2787,2824,2827,
2866,2886,2920,2957,3022,3068,3127,3137,3264,3272,3282,3340,3342,3349,3402,3404,3408,3419,3427,3429,3437,3454,3516,3518,3520,3525,
3526,3554,3719,3742,3773,3798,3817,3821,4109,4151,4205,4215,4277,4295,4310,4316,4323,4410,4432,4487,4504,4526,4551,4552,4571,4590,
4613,4619,4624,4648,4748,4777,4791,4808,4850,4911,5014,5033,5080,5108,5130,5141,5180,5204,5214,5217,5241,5259,5311,5331,5356,5408,
5431,5462,5468,5517,5553,5558,5569,5641,5655,5667,5676,5696,5765,5768,5790,5840,5859,5878,6001,6061,6069,6116,6145,6258,6428,6466,
6469,6476,6502,6519,6535,6608,6671,6678,6686,6756,6844,6871,6984,7010,7017,7050,7089,7093,7190,7214,7252,7285,7300,7310,7400,7417,
7476,7510,7530,7551,7600,7656,7701,7741,7756,7797,7800,7866,7876,7901,7971,8004,8012,8082,8089,8121,8179,8211,8218,8244,8371,8406,
8412,8455,8530,8544,8558,8596,8688,8700,8791,8831,8833,8852,8866,8880,8891,8967,9002,9052,9074,9099,9140,9306,9392,9511,9545,9800,
9808,9822,94,132,175,196,231,234,288,300,352,387,500,652,783,892,944,1462,1464,1659,1685,1742,1767,1769,1853,1872,
1891,2159,2171,2182,2186,2190,2264,2283,2289,2292,2352,2386,2387,2438,2459,2463,2560,2564,2571,2572,2584,2599,2647,2664,2691,2740,
2752,2759,2791,2795,2799,2821,2830,2831,2842,2850,2869,2885,2892,2917,2969,2988,3023,3136,3140,3143,3170,3205,3226,3308,3368,3378,
3393,3416,3428,3450,3461,3469,3539,3551,3565,3571,3610,3645,3646,3649,3667,3686,3695,3696,3715,3850,3944,3993,4002,4027,4029,4045,
4120,4132,4156,4169,4216,4236,4251,4269,4337,4434,4470,4472,4549,4612,4615,4632,4694,4720,4728,4811,4825,4826,4849,4852,5015,5019,
5064,5132,5171,5188,5201,5220,5269,5276,5277,5285,5288,5300,5318,5326,5342,5426,5467,5481,5536,5552,5562,5587,5590,5606,5660,5702,
5712,5759,5804,5847,5866,5895,5898,5906,6160,6231,6264,6279,6289,6368,6421,6424,6441,6462,6481,6675,6680,6682,6730,6747,6784,6914,
7114,7140,7152,7221,7273,7283,7333,7387,7401,7409,7585,7607,7625,7633,7709,7713,7725,7767,7849,8101,8127,8188,8216,8221,8240,8287,
8352,8510,8625,8687,8756,8819,8844,8846,9007,9182,9300,9497,9507,9566,9594,9610,9665,9764,9868,9872,9888,38,48,150,154,156,
172,177,233,246,287,484,889,970,1294,1392,1449,1483,1497,1498,1539,1558,1630,1640,1799,2069,2084,2095,2184,2189,2193,
2197,2259,2295,2363,2373,2445,2490,2495,2540,2558,2562,2581,2616,2618,2629,2630,2642,2644,2645,2654,2661,2716,2726,2731,2736,2747,
2790,2822,2875,2898,2921,2934,2950,2956,3018,3066,3156,3230,3238,3319,3350,3360,3365,3370,3407,3431,3440,3514,3544,3555,3568,3591,
3635,3713,3787,3839,3877,3891,4035,4080,4119,4143,4184,4204,4222,4314,4328,4331,4341,4355,4371,4405,4423,4451,4480,4483,4485,4537,
4577,4579,4580,4598,4652,4660,4662,4684,4701,4731,4788,4792,4820,4823,4832,4853,4878,4936,4959,4972,4979,4991,5012,5088,5089,5090,
5125,5164,5272,5279,5292,5346,5351,5358,5416,5435,5475,5501,5520,5559,5580,5584,5591,5598,5629,5647,5679,5682,5747,5748,5752,5771,
5811,5874,5891,5983,6012,6033,6066,6099,6100,6101,6122,6163,6179,6223,6224,6226,6248,6446,6456,6463,6512,6530,6532,6537,6546,6547,
6569,6601,6673,6711,6819,6866,6878,6946,6955,6976,7005,7130,7173,7185,7311,7378,7388,7403,7454,7473,7590,7606,7666,7689,7716,7724,
7751,7783,7802,7921,7952,7978,8016,8134,8176,8190,8277,8288,8347,8348,8385,8404,8409,8464,8471,8475,8480,8485,8494,8505,8515,8531,
8740,8818,8823,8878,8963,8969,9021,9069,9098,9116,9198,9263,9290,9423,9527,9541,9653,9659,9698,9787,9879,9901,9910,9923,9975,34,
81,141,249,256,257,270,455,655,700,865,957,969,997,1393,1582,1681,1755,1792,1866,1895,2066,2167,2195,2260,2361,2371,
2384,2398,2440,2634,2646,2659,2674,2685,2730,2762,2766,2784,2841,2913,2928,2940,2975,2992,3027,3028,3041,3050,3149,3188,3190,3197,
3228,3239,3249,3257,3307,3371,3372,3413,3458,3460,3465,3488,3489,3509,3626,3632,3638,3640,3701,3718,3789,3816,3822,3875,3978,4051,
4062,4101,4154,4218,4220,4227,4240,4250,4278,4409,4413,4439,4449,4452,4458,4464,4468,4471,4475,4510,4517,4525,4595,4678,4685,4712,
4714,4729,4794,4813,4891,4909,4950,5027,5040,5074,5077,5082,5107,5147,5205,5216,5226,5227,5239,5240,5271,5320,5347,5363,5390,5439,
5444,5476,5485,5515,5572,5626,5630,5634,5652,5666,5675,5769,5821,5894,5896,5950,5989,5995,6015,6040,6191,6234,6250,6261,6272,6276,
6277,6290,6355,6367,6400,6431,6485,6553,6574,6600,6623,6624,6679,6696,6782,6788,6810,6913,7003,7033,7120,7201,7266,7302,7376,7383,
7427,7471,7479,7509,7598,7655,7710,7745,7805,7821,7862,7864,7874,7888,7910,7991,8077,8109,8192,8201,8202,8219,8279,8283,8338,8514,
8516,8567,8569,8584,8701,8710,8712,8715,8749,8790,8805,8879,8897,8922,8946,8974,9190,9211,9239,9399,9411,9619,9636,9663,9718,9807,
9811,9845,9927,9937,9944,9982,9984,30,36,133,135,148,162,165,245,269,347,349,358,364,482,567,592,678,744,747,
786,844,854,932,937,1097,1650,1655,1662,1696,1756,1759,1763,1768,1831,1851,1854,1867,2054,2092,2158,2198,2267,2537,2544,2557,
2573,2595,2632,2637,2676,2680,2687,2754,2778,2783,2794,2871,2876,2877,2919,2939,2979,2986,3056,3167,3185,3187,3276,3347,3359,3401,
3409,3417,3439,3441,3459,3508,3517,3564,3566,3572,3631,3641,3650,3665,3670,3679,3681,3738,3739,3801,3833,3843,3845,3884,3940,4118,
4155,4180,4207,4208,4226,4247,4286,4300,4315,4351,4419,4453,4462,4506,4515,4522,4534,4541,4585,4679,4689,4721,4863,4888,4951,5038,
5041,5091,5101,5135,5140,5174,5224,5229,5258,5293,5324,5344,5414,5434,5446,5487,5505,5506,5589,5620,5622,5643,5644,5648,5661,5664,
5668,5686,5697,5700,5714,5787,5819,5820,5824,5843,5953,5955,5970,5985,5988,6021,6029,6102,6115,6150,6166,6214,6220,6256,6397,6513,
6523,6567,6602,6707,6888,6918,6966,6981,7012,7020,7071,7104,7175,7265,7367,7406,7413,7449,7497,7501,7525,7621,7622,7640,7648,7772,
7796,7858,7908,7956,7964,7977,8014,8025,8073,8182,8205,8250,8251,8260,8284,8285,8314,8366,8401,8410,8427,8524,8541,8611,8629,8706,
8876,8887,8911,8958,8990,8993,9017,9020,9106,9188,9345,9355,9414,9449,9533,9544,9561,9575,9631,9709,9756,9786,9809,9820,9842,9849,
9851,9864,9890,9897,9925,9980,9992,9993,56,93,169,241,274,356,441,477,774,779,898,931,955,976,1373,1439,1491,1493,
1581,1697,1753,1765,1782,1858,2058,2068,2082,2172,2176,2249,2296,2339,2376,2382,2449,2476,2498,2499,2538,2556,2591,2656,2678,2724,
2744,2788,2792,2840,2861,2878,2880,2955,2974,2985,3087,3139,3154,3177,3191,3269,3351,3354,3391,3397,3475,3502,3538,3552,3560,3606,
3621,3623,3630,3648,3662,3680,3684,3697,3714,3819,3827,3831,3832,3855,3888,3912,3931,4005,4023,4026,4028,4116,4135,4190,4233,4252,
4262,4266,4285,4324,4352,4406,4426,4443,4482,4527,4542,4610,4688,4713,4750,4757,4844,4876,4923,4957,4973,4977,4982,4987,5030,5042,
5114,5138,5143,5172,5184,5189,5203,5218,5228,5266,5283,5295,5322,5384,5401,5428,5452,5457,5459,5471,5474,5489,5526,5534,5542,5568,
5616,5618,5733,5755,5832,5842,5850,5857,5864,5899,5911,5913,5937,5986,6007,6008,6162,6235,6255,6283,6312,6341,6404,6413,6468,6521,
6575,6647,6755,6758,6765,6777,6787,6845,6909,6974,6980,7024,7042,7051,7113,7129,7139,7147,7155,7157,7174,7183,7276,7288,7305,7312,
7318,7329,7425,7444,7445,7465,7470,7480,7488,7504,7543,7559,7566,7574,7669,7679,7703,7719,7738,7742,7818,7883,7907,7926,7965,8020,
8056,8084,8110,8125,8157,8183,8275,8289,8304,8389,8436,8451,8491,8501,8555,8576,8582,8587,8595,8684,8821,8843,8907,8923,8976,9004,
9170,9293,9327,9363,9505,9518,9565,9582,9600,9623,9777,9791,9887,9891,9896,9914,9957,9964,9976,91,97,182,240,255,272,279,
338,450,453,534,748,780,792,871,948,981,1039,1651,1667,1737,1741,1761,1798,1839,1857,2038,2061,2086,2089,2173,2183,2271,
2446,2471,2496,2641,2670,2694,2748,2771,2775,2835,2879,2887,2890,2891,2951,2980,2990,3044,3075,3175,3260,3262,3329,3364,3383,3471,
3479,3490,3531,3548,3557,3559,3567,3605,3644,3700,3712,3728,3763,3807,3812,3834,3837,3887,3890,3901,3938,3982,3999,4030,4096,4117,
4145,4159,4164,4172,4177,4209,4253,4272,4301,4403,4465,4494,4502,4514,4518,4519,4531,4584,4617,4659,4787,4798,4858,4887,4900,4941,
5003,5008,5018,5044,5045,5053,5113,5118,5142,5199,5237,5244,5247,5264,5294,5298,5352,5357,5378,5392,5407,5460,5531,5570,5651,5681,
5688,5776,5786,5827,5829,5833,5887,5904,5908,5931,5977,6011,6031,6222,6227,6232,6265,6285,6318,6326,6389,6406,6533,6590,6639,6681,
6689,6700,6705,6740,6752,6876,6877,6891,6967,7121,7131,7144,7176,7262,7303,7319,7355,7375,7393,7517,7578,7595,7619,7687,7705,7731,
7761,7785,7810,8003,8029,8030,8143,8191,8212,8324,8332,8381,8391,8414,8420,8482,8488,8552,8565,8590,8633,8689,8774,8870,8874,8902,
8908,8949,8968,8981,9067,9118,9128,9166,9184,9192,9288,9295,9296,9298,9456,9569,9605,9721,9834,9847,9880,9922,9978,9986,52,85,
155,167,184,238,247,341,354,386,493,574,897,986,991,995,1549,1576,1653,1673,1748,1764,1797,2039,2091,2097,2152,2492,
2643,2690,2698,2757,2785,2826,2832,2836,2858,2883,2927,2931,2932,2977,2981,2996,3016,3034,3036,3098,3146,3171,3183,3186,3248,3296,
3362,3376,3438,3446,3463,3468,3480,3485,3493,3507,3523,3627,3629,3642,3647,3678,3685,3688,3722,3786,3813,3846,3928,3933,4003,4019,
4060,4069,4108,4170,4188,4196,4260,4265,4292,4342,4346,4357,4382,4457,4499,4507,4557,4576,4671,4733,4765,4784,4806,4836,4847,4851,
4856,4874,4880,4886,5031,5122,5149,5158,5215,5243,5261,5289,5307,5317,5360,5397,5469,5491,5498,5524,5529,5541,5550,5561,5581,5611,
5658,5710,5723,5761,5770,5785,5810,5826,5860,5877,5901,6010,6022,6062,6068,6119,6128,6133,6244,6311,6333,6350,6351,6422,6452,6480,
6557,6645,6690,6710,6721,6772,6791,6837,6867,6901,6985,7127,7128,7138,7207,7219,7244,7275,7298,7327,7404,7467,7472,7515,7601,7608,
7613,7691,7720,7736,7768,7795,7903,8005,8017,8034,8037,8044,8128,8148,8150,8189,8200,8204,8220,8238,8242,8351,8422,8478,8545,8566,
8622,8698,8726,8741,8750,8777,8801,8813,8841,8865,8987,8997,9030,9114,9145,9163,9193,9229,9264,9442,9448,9501,9524,9536,9580,9598,
9639,9738,9747,9883,9934,53,61,62,149,171,232,251,361,371,372,445,560,645,660,686,888,963,984,1495,1499,1557,
1695,1746,1766,1846,2042,2071,2072,2074,2075,2078,2079,2261,2270,2381,2396,2640,2649,2671,2758,2774,2780,2893,2933,2995,3045,3053,
3165,3176,3268,3271,3284,3285,3348,3361,3384,3464,3466,3481,3550,3576,3581,3596,3597,3608,3616,3619,3633,3643,3659,3673,3682,3724,
3730,3732,3743,3751,3766,3783,3785,3815,3842,3935,3975,4008,4105,4129,4131,4178,4195,4229,4263,4338,4345,4378,4398,4401,4459,4467,
4508,4530,4597,4631,4645,4650,4669,4690,4745,4751,4759,4772,4807,4854,4859,4893,4913,4916,4937,4939,5023,5029,5034,5056,5139,5145,
5166,5175,5297,5301,5314,5345,5379,5391,5402,5422,5437,5453,5484,5502,5516,5582,5614,5663,5671,5691,5709,5750,5764,5818,5823,5876,
5927,5999,6020,6035,6113,6186,6187,6189,6212,6213,6246,6269,6284,6313,6361,6362,6386,6410,6415,6454,6474,6482,6518,6642,6698,6714,
6781,6800,6824,6825,6833,6852,6879,6882,6898,6907,6915,6979,6991,7013,7057,7082,7109,7115,7132,7205,7226,7239,7263,7269,7364,7389,
7424,7433,7469,7502,7521,7539,7545,7558,7565,7646,7665,7702,7715,7723,7792,7808,7823,7827,7928,7929,7966,7976,8024,8086,8087,8105,
8124,8193,8213,8222,8227,8281,8291,8302,8382,8388,8452,8518,8546,8550,8563,8591,8617,8690,8754,8755,8766,8796,8797,8817,8832,8858,
8883,8885,8886,8928,8944,8956,9062,9137,9194,9210,9218,9247,9252,9279,9321,9324,9346,9348,9366,9371,9514,9586,9613,9701,9733,9739,
9818,9836,9854,9908,9950,9968,47,54,57,65,67,136,271,278,355,378,400,444,451,454,551,564,732,869,885,891,
959,998,1658,1672,1757,1791,2036,2037,2041,2059,2383,2598,2660,2673,2675,2738,2756,2769,2776,2798,2838,2847,2852,2884,2914,2941,
2942,2968,2982,2984,3026,3072,3077,3088,3138,3178,3295,3374,3385,3398,3405,3532,3561,3562,3601,3653,3656,3717,3726,3729,3740,3747,
3756,3757,3775,3826,3835,3859,3869,3880,3936,3972,3990,3995,4147,4257,4267,4284,4290,4302,4318,4319,4335,4369,4427,4428,4478,4492,
4524,4558,4599,4622,4658,4715,4718,4719,4732,4768,4771,4801,4830,4881,4895,4958,4983,4997,5006,5026,5043,5058,5085,5087,5134,5181,
5219,5275,5305,5323,5359,5387,5436,5442,5447,5450,5470,5482,5492,5496,5509,5519,5539,5571,5592,5601,5604,5613,5617,5659,5708,5716,
5727,5762,5778,5780,5782,5783,5799,5801,5822,5862,5863,5865,5868,5897,5932,5962,5990,6009,6025,6027,6044,6050,6104,6170,6185,6221,
6228,6242,6270,6329,6331,6345,6365,6419,6460,6470,6484,6514,6516,6517,6534,6577,6578,6582,6586,6670,6762,6770,6771,6870,6884,6885,
6889,6923,6958,6965,7006,7015,7025,7045,7047,7145,7164,7178,7212,7220,7232,7234,7257,7280,7282,7287,7290,7335,7419,7422,7423,7440,
7441,7455,7484,7485,7505,7508,7524,7536,7546,7573,7586,7587,7588,7623,7658,7708,7781,7784,7884,7919,7963,8015,8046,8083,8103,8114,
8166,8199,8245,8255,8256,8267,8286,8305,8317,8319,8321,8325,8342,8345,8402,8431,8522,8532,8562,8579,8632,8662,8694,8769,8785,8799,
8825,8847,8853,8868,8896,8921,8937,8985,8986,8999,9082,9088,9102,9121,9165,9216,9222,9317,9368,9546,9579,9588,9611,9666,9685,9687,
9758,9774,9790,9824,9831,9915,9920,9921,9973,96,170,174,239,267,281,286,350,365,476,478,487,488,495,542,546,569,
576,600,653,654,657,683,750,771,973,1639,1758,1779,1868,2062,2073,2083,2191,2372,2393,2549,2559,2592,2596,2619,2683,2695,
2739,2745,2751,2760,2763,2849,2959,2960,2965,2973,2989,3029,3058,3062,3069,3096,3151,3173,3181,3192,3229,3275,3289,3382,3387,3389,
3390,3418,3447,3470,3484,3540,3599,3609,3617,3634,3661,3668,3689,3705,3716,3725,3741,3746,3748,3848,3865,3915,3919,3984,3987,3994,
4009,4018,4025,4039,4059,4066,4148,4163,4187,4194,4217,4249,4259,4264,4280,4282,4308,4326,4330,4350,4363,4387,4447,4461,4490,4528,
4573,4581,4583,4593,4596,4637,4644,4665,4673,4677,4686,4691,4753,4760,4781,4882,4910,4918,4921,4999,5054,5071,5131,5159,5163,5170,
5176,5182,5208,5260,5265,5299,5309,5316,5334,5369,5370,5372,5388,5479,5483,5596,5615,5619,5637,5650,5690,5756,5760,5767,5792,5798,
5816,5830,5831,5836,5839,5854,5889,5892,5900,5910,5987,6024,6114,6134,6169,6199,6230,6292,6295,6323,6324,6340,6377,6398,6427,6504,
6531,6555,6598,6606,6612,6625,6649,6674,6719,6725,6731,6774,6849,6859,6910,6959,6997,7027,7072,7088,7118,7133,7208,7213,7228,7248,
7271,7279,7296,7325,7334,7382,7416,7420,7446,7452,7457,7468,7482,7518,7529,7540,7541,7548,7591,7596,7645,7650,7659,7798,7857,7868,
7881,7893,7915,7985,7998,8006,8009,8022,8023,8033,8040,8085,8102,8115,8116,8117,8120,8130,8155,8168,8187,8209,8226,8237,8257,8290,
8300,8316,8367,8433,8469,8499,8528,8683,8772,8830,8842,8950,8970,9003,9013,9025,9040,9050,9155,9203,9213,9227,9281,9357,9395,9410,
9486,9506,9523,9557,9567,9577,9693,9697,9699,9710,9712,9722,9784,9802,9819,9830,9873,9902,9917,9918,9924,9965,9997,39,46,236,
254,260,297,332,336,432,440,539,582,661,667,754,769,788,790,935,943,951,962,1660,1738,1751,1843,2043,2194,2392,
2593,2681,2699,2786,2845,2865,2872,2874,2889,2915,2938,2953,2966,3019,3048,3054,3071,3079,3099,3148,3189,3193,3274,3395,3396,3503,
3527,3558,3574,3582,3586,3706,3736,3758,3764,3836,3893,3924,3962,4014,4016,4087,4134,4139,4166,4175,4181,4203,4230,4254,4271,4283,
4293,4327,4353,4373,4377,4429,4509,4538,4602,4625,4667,4697,4698,4707,4734,4744,4749,4752,4779,4796,4802,4804,4822,4840,4845,4857,
4875,4885,4902,4919,4924,4966,4969,4974,5049,5059,5079,5106,5281,5290,5329,5381,5427,5670,5680,5724,5730,5797,5805,5848,5855,5890,
5914,5961,6002,6004,6046,6088,6129,6130,6147,6177,6190,6201,6215,6219,6233,6236,6287,6293,6315,6319,6339,6387,6392,6433,6444,6445,
6489,6507,6524,6579,6589,6605,6613,6618,6632,6648,6684,6811,6820,6872,6881,6887,6922,6925,7008,7058,7067,7122,7125,7154,7158,7163,
7199,7222,7237,7240,7259,7289,7342,7351,7379,7390,7481,7523,7528,7555,7561,7569,7630,7653,7684,7748,7753,7791,7794,7809,7819,7847,
7900,7905,7922,7923,7983,7984,8098,8106,8135,8147,8214,8248,8298,8372,8405,8407,8416,8474,8537,8559,8564,8574,8716,8731,8745,8771,
8816,8871,8873,9024,9101,9113,9122,9180,9204,9254,9349,9401,9424,9452,9458,9481,9502,9547,9584,9634,9742,9750,9760,9792,9886,9931,
9994,37,50,59,86,161,163,178,198,252,275,276,339,375,391,457,459,462,474,489,533,561,562,563,570,586,
587,599,668,846,958,1494,1496,1646,1656,1698,1749,1762,1796,2053,2098,2397,2553,2732,2734,2743,2770,2796,2926,2945,2978,3037,
3153,3195,3252,3381,3473,3563,3573,3593,3602,3675,3676,3677,3779,3795,3806,3828,3853,3863,3892,3910,3937,3941,3946,3977,4103,4104,
4136,4146,4153,4270,4347,4367,4388,4393,4430,4438,4505,4594,4609,4614,4616,4621,4633,4670,4709,4723,4741,4758,4773,4783,4786,4824,
4835,4846,4872,4873,4883,4908,4980,5046,5127,5161,5187,5332,5341,5350,5368,5409,5430,5518,5530,5547,5573,5609,5662,5736,5779,5828,
5849,5851,5867,5875,5884,5886,5922,5998,6030,6083,6107,6118,6143,6181,6184,6188,6198,6257,6263,6274,6282,6294,6317,6337,6418,6432,
6477,6483,6515,6520,6563,6583,6587,6593,6599,6604,6616,6630,6672,6773,6812,6814,6858,6932,6992,7075,7086,7119,7161,7170,7197,7206,
7231,7258,7278,7328,7407,7492,7503,7564,7614,7660,7672,7728,7732,7760,7790,7803,7815,7844,7851,7855,7916,7918,7933,7973,8050,8053,
8079,8145,8177,8198,8235,8241,8253,8274,8303,8327,8337,8400,8445,8526,8580,8607,8627,8670,8806,8882,8895,9029,9093,9120,9158,9177,
9181,9215,9219,9256,9294,9299,9365,9377,9389,9412,9421,9462,9464,9465,9491,9496,9560,9599,9604,9622,9658,9796,9798,9803,9848,9885,
9972,9983,40,43,151,164,244,284,285,289,290,360,370,552,554,566,669,688,695,798,877,882,939,2081,2293,2494,
2594,2597,2655,2696,2735,2782,2854,2860,2896,2897,2944,2949,2970,2991,3039,3051,3064,3084,3196,3273,3290,3392,3448,3494,3598,3607,
3620,3655,3664,3731,3735,3745,3784,3793,3829,3851,3860,3874,3895,3922,3949,3963,3979,4068,4072,4140,4173,4189,4241,4275,4281,4317,
4336,4348,4379,4380,4391,4395,4435,4476,4529,4553,4681,4683,4687,4739,4755,4756,4770,4793,4810,4818,4819,4831,4838,4841,4890,4896,
4912,4914,4954,4964,5037,5075,5167,5173,5198,5313,5343,5443,5499,5532,5672,5719,5741,5753,5951,5971,5981,6124,6144,6148,6171,6241,
6243,6268,6374,6401,6442,6493,6509,6568,6584,6621,6631,6692,6743,6750,6754,6766,6808,6809,6815,6839,6855,6875,6894,6921,6928,6933,
6951,6983,6998,7014,7029,7030,7069,7073,7078,7096,7098,7159,7166,7217,7292,7361,7371,7402,7408,7426,7513,7553,7567,7649,7651,7657,
7688,7706,7793,7825,7833,7848,7886,8140,8159,8164,8215,8231,8243,8266,8269,8320,8393,8403,8503,8506,8507,8508,8547,8600,8616,8645,
8664,8672,8676,8691,8713,8770,8786,8793,8802,8913,8916,8933,8971,8979,8980,8992,8994,9019,9031,9041,9077,9147,9153,9187,9199,9202,
9221,9226,9238,9422,9439,9455,9490,9542,9559,9585,9597,9614,9635,9652,9672,9691,9705,9810,9903,9904,9956,9961,9963,9971,58,84,
193,268,291,335,367,383,398,458,469,759,772,787,841,848,850,868,873,876,896,1694,1752,1794,1795,2087,2638,2651,
2682,2697,2741,2749,2761,2764,2765,2797,2844,2863,2870,2954,2963,2971,2997,3043,3057,3061,3074,3082,3194,3483,3583,3657,3694,3769,
3770,3788,3799,3820,3844,3867,3876,3886,3908,3916,3917,3989,3996,4006,4031,4032,4036,4057,4149,4158,4192,4198,4246,4261,4294,4303,
4306,4375,4385,4436,4491,4559,4592,4606,4626,4640,4651,4668,4716,4727,4780,4834,4871,4877,4889,4915,4952,4960,4971,4976,5048,5078,
5183,5190,5249,5267,5303,5364,5371,5448,5449,5473,5527,5692,5701,5722,5772,5784,5802,5813,5814,5870,5883,5907,5924,5941,5945,5952,
5965,5968,5975,5991,6003,6067,6070,6105,6117,6136,6153,6158,6168,6175,6204,6217,6273,6302,6305,6314,6334,6352,6354,6381,6383,6443,
6457,6494,6510,6549,6627,6657,6693,6733,6790,6828,6832,6840,6848,6926,6930,6934,6944,6960,6973,6990,7034,7126,7135,7143,7146,7156,
7195,7204,7223,7224,7225,7229,7233,7247,7253,7254,7264,7268,7270,7308,7309,7320,7331,7357,7359,7372,7464,7507,7563,7582,7584,7594,
7627,7675,7680,7697,7729,7752,7806,7826,7839,7863,7885,7914,7934,7936,7995,8019,8031,8042,8060,8169,8170,8178,8208,8217,8236,8265,
8271,8292,8307,8308,8322,8358,8408,8415,8444,8457,8527,8533,8534,8535,8581,8583,8604,8618,8626,8651,8654,8660,8667,8692,8742,8815,
8836,8856,8863,8914,8931,8934,8965,8978,9070,9083,9092,9133,9135,9150,9154,9175,9196,9232,9250,9255,9286,9303,9331,9354,9400,9427,
9463,9474,9478,9479,9531,9563,9568,9591,9618,9662,9678,9689,9700,9761,9855,9929,9985,176,262,263,470,475,483,491,540,573,
594,634,640,776,782,799,1859,2742,2746,2753,2895,2923,2936,2947,2948,2958,3047,3085,3495,3506,3530,3584,3603,3687,3720,3734,
3753,3765,3767,3781,3864,3870,3885,3889,3948,4047,4054,4084,4099,4137,4191,4197,4199,4238,4340,4359,4397,4496,4498,4574,4608,4639,
4641,4661,4708,4740,4746,4754,4762,4816,4828,4925,4942,4947,4953,4988,4992,5009,5069,5072,5119,5207,5238,5278,5287,5490,5653,5684,
5695,5699,5717,5773,5807,5815,5845,5853,5872,5893,5917,5926,5943,6016,6135,6146,6156,6174,6205,6216,6259,6260,6322,6327,6347,6378,
6402,6475,6558,6603,6617,6635,6691,6718,6742,6779,6847,6899,6917,6941,6948,6962,6995,7028,7031,7055,7074,7092,7107,7160,7180,7230,
7251,7281,7299,7315,7317,7323,7353,7380,7432,7459,7514,7560,7568,7571,7589,7609,7615,7735,7750,7754,7764,7828,7842,7875,7906,7925,
7940,7955,7974,8026,8160,8163,8173,8197,8232,8233,8299,8309,8315,8323,8330,8370,8375,8379,8386,8446,8458,8465,8490,8529,8674,8703,
8719,8720,8727,8733,8827,8872,8918,8930,8966,9027,9079,9144,9146,9168,9231,9251,9301,9315,9323,9335,9417,9420,9453,9484,9516,9517,
9522,9657,9714,9832,173,181,186,277,280,295,448,547,572,578,585,633,642,682,698,753,755,785,838,883,893,966,
2672,2943,2983,2994,3038,3097,3174,3263,3346,3487,3491,3604,3671,3674,3759,3782,3805,3830,3847,3856,3878,3881,3882,3909,3913,3921,
3930,3959,3961,3969,3985,4071,4074,4090,4098,4165,4287,4289,4298,4349,4366,4399,4463,4479,4503,4627,4635,4702,4870,4903,4955,4961,
4998,5065,5081,5109,5148,5179,5273,5383,5493,5540,5597,5605,5636,5638,5721,5744,5979,6014,6090,6132,6176,6195,6267,6281,6330,6332,
6375,6409,6416,6450,6451,6459,6479,6522,6564,6597,6615,6628,6641,6646,6651,6659,6722,6741,6794,6897,6903,7044,7062,7181,7193,7267,
7297,7307,7322,7347,7429,7431,7537,7581,7686,7746,7763,7814,7832,7871,7951,8075,8138,8154,8247,8249,8263,8293,8335,8340,8378,8413,
8417,8428,8460,8571,8593,8613,8621,8722,8761,8762,8780,8782,8807,8894,8915,8929,8938,8945,8964,8996,9026,9044,9056,9057,9095,9096,
9132,9134,9230,9234,9262,9398,9405,9428,9444,9476,9499,9558,9601,9638,9649,9654,9704,9707,9727,9754,9767,9776,9782,9785,9907,9913,
9935,9953,9960,273,359,396,435,452,463,467,468,556,579,580,590,598,664,676,677,699,742,757,764,834,965,974,
993,1693,1847,2692,2768,2857,2859,2862,2899,2924,2962,2976,2998,3059,3078,3083,3172,3482,3492,3723,3755,3861,3862,3866,3902,3926,
3952,3957,3966,3968,3988,4034,4049,4052,4061,4082,4107,4174,4183,4186,4273,4297,4299,4304,4339,4384,4389,4636,4642,4643,4675,4676,
4692,4705,4717,4736,4763,4795,4799,4805,4837,4898,4906,4922,4946,4956,4984,4985,5016,5083,5095,5128,5136,5206,5286,5296,5302,5367,
5380,5382,5399,5403,5405,5429,5480,5508,5537,5583,5594,5631,5640,5649,5718,5751,5766,5834,5856,5915,5918,5923,6032,6037,6106,6108,
6121,6159,6208,6299,6301,6335,6349,6373,6388,6423,6426,6436,6471,6487,6499,6550,6561,6580,6581,6640,6728,6759,6802,6880,6892,6908,
6936,6950,6961,6975,6982,7016,7039,7076,7079,7134,7168,7184,7191,7215,7216,7243,7291,7294,7341,7352,7356,7368,7381,7428,7489,7496,
7542,7547,7550,7634,7681,7685,7690,7692,7699,7739,7743,7804,7859,7924,7941,7945,7950,7954,7986,8099,8122,8129,8175,8224,8254,8261,
8262,8328,8373,8380,8390,8419,8454,8481,8483,8495,8540,8549,8570,8605,8608,8615,8657,8659,8661,8663,8665,8685,8704,8707,8709,8730,
8752,8753,8763,8764,8775,8820,8854,8859,8909,8924,9018,9045,9060,9089,9104,9105,9124,9162,9176,9179,9233,9248,9267,9309,9336,9383,
9396,9403,9408,9426,9437,9440,9451,9487,9495,9504,9552,9562,9603,9612,9651,9667,9706,9723,9751,9765,9775,9783,9823,9860,9867,9882,
9905,9941,9952,185,397,399,433,434,437,464,466,536,549,558,658,680,697,737,758,773,835,862,870,875,934,936,
992,2693,2793,2867,2937,2952,2961,3067,3293,3595,3774,3778,3780,3852,3857,3868,3905,3958,3970,3991,4043,4046,4053,4067,4089,4106,
4167,4182,4193,4237,4276,4291,4358,4364,4437,4473,4572,4607,4724,4726,4843,4899,4917,4948,4995,5063,5186,5197,5274,5340,5607,5642,
5685,5694,5705,5734,5737,5803,5916,5944,5973,5974,6019,6045,6063,6080,6149,6151,6202,6253,6342,6358,6360,6467,6472,6473,6478,6527,
6585,6591,6595,6596,6634,6701,6739,6745,6753,6938,6945,7048,7060,7087,7105,7153,7246,7261,7284,7316,7366,7430,7463,7506,7534,7570,
7592,7617,7642,7663,7696,7813,7953,7970,7972,7975,8027,8054,8066,8071,8142,8185,8195,8223,8273,8280,8473,8479,8519,8554,8599,8603,
8610,8631,8655,8693,8835,8840,8845,8917,9005,9053,9055,9075,9078,9103,9142,9169,9223,9242,9277,9284,9318,9319,9322,9338,9431,9443,
9466,9503,9521,9553,9602,9644,9676,9684,9719,9720,9757,9766,9771,9781,9793,9814,9825,9841,9844,9869,9881,9884,9970,51,139,194,
264,265,363,376,382,471,472,494,568,581,632,641,752,761,797,840,887,895,953,956,983,996,2394,2851,2993,3052,
3065,3092,3095,3292,3449,3496,3704,3762,3771,3797,3804,3956,3973,4076,4086,4094,4162,4296,4307,4360,4361,4362,4407,4481,4630,4638,
4693,4735,4767,4814,4892,4920,4975,5047,5057,5096,5098,5137,5178,5185,5327,5395,5608,5703,5732,5795,5873,5920,5930,5954,5976,5984,
6005,6127,6141,6152,6178,6196,6218,6240,6291,6344,6371,6379,6393,6435,6437,6505,6551,6552,6607,6614,6619,6703,6708,6715,6716,6717,
6751,6757,6780,6798,6883,6916,6956,7019,7035,7040,7081,7106,7124,7249,7255,7295,7343,7369,7398,7442,7451,7487,7499,7516,7522,7526,
7544,7626,7671,7674,7816,7822,7846,7917,7932,7943,7960,7961,7969,8032,8171,8206,8225,8230,8368,8399,8423,8442,8463,8470,8476,8536,
8561,8601,8644,8658,8671,8699,8758,8804,8838,8851,8861,8862,8904,8959,8984,9028,9072,9109,9127,9195,9214,9272,9280,9314,9328,9369,
9387,9388,9404,9425,9461,9470,9493,9525,9530,9537,9646,9648,9717,9724,9741,9745,9746,9752,9795,9840,9895,160,394,395,461,490,
545,583,631,637,650,662,733,765,791,881,886,938,967,2076,2096,3297,3808,3871,3923,3965,3997,4038,4138,4368,4376,4408,
4623,4821,4907,4938,4944,4978,4990,5092,5338,5704,5720,5739,5745,5796,5902,5942,5964,6034,6048,6051,6065,6074,6238,6308,6320,6348,
6356,6380,6417,6501,6503,6562,6571,6572,6588,6620,6643,6796,6821,6830,6902,6943,6952,6957,7009,7053,7099,7165,7182,7203,7236,7241,
7242,7314,7392,7498,7670,7801,7837,7870,7968,8038,8091,8141,8144,8162,8297,8306,8341,8353,8418,8430,8450,8556,8597,8640,8677,8695,
8767,8826,8834,8860,8867,8942,8943,8955,9152,9157,9161,9224,9278,9285,9291,9341,9441,9508,9520,9554,9556,9590,9627,9641,9642,9671,
9675,9686,9749,9806,9829,9837,9853,9936,9945,9954,9959,334,353,373,379,481,497,541,553,644,649,796,832,833,858,874,
941,946,968,971,2051,2843,2964,2967,3081,3529,3549,3589,3744,3858,3897,3974,3976,4058,4070,4075,4088,4239,4370,4394,4396,4706,
4743,4766,4782,4809,4897,4931,4933,4935,4981,5035,5061,5062,5192,5374,5385,5495,5725,5728,5731,5738,5742,5774,5835,5837,5871,5909,
5949,5997,6042,6081,6103,6172,6252,6278,6414,6429,6430,6491,6506,6536,6652,6702,6834,6860,6865,6931,6953,6986,7066,7083,7108,7286,
7324,7338,7344,7363,7384,7385,7395,7405,7437,7483,7490,7494,7520,7527,7572,7631,7820,7831,7840,7841,7853,7957,8028,8049,8094,8151,
8156,8161,8239,8331,8360,8361,8369,8377,8392,8434,8441,8466,8497,8517,8543,8602,8614,8623,8630,8639,8681,8708,8732,8734,8757,8784,
8803,8857,8906,8975,9016,9039,9059,9061,9086,9094,9156,9160,9164,9171,9172,9220,9235,9237,9258,9260,9270,9274,9283,9332,9356,9438,
9450,9532,9625,9674,9692,9794,9826,9828,9859,9866,9894,9930,9943,9949,9958,9962,9967,197,237,253,368,388,648,665,685,739,
740,884,899,3073,3497,3592,3709,3920,3954,3992,4065,4091,4092,4374,4495,4672,4776,4829,4894,4929,4993,5066,5067,5319,5349,5361,
5396,5627,5740,5794,5919,5939,5958,6180,6203,6207,6209,6239,6271,6309,6370,6395,6447,6448,6458,6526,6576,6709,6746,6838,6841,6861,
6864,6873,6924,6993,7186,7209,7238,7397,7583,7641,7694,7762,7836,7992,8062,8069,8096,8132,8136,8139,8165,8333,8387,8439,8440,8606,
8609,8682,8696,8724,8905,8932,8954,9042,9189,9243,9259,9266,9271,9275,9316,9325,9372,9397,9471,9540,9571,9661,9688,9708,9716,9763,
9770,9780,9838,183,195,348,366,449,465,473,543,591,636,638,656,687,694,781,837,857,861,863,867,950,952,954,
3094,3394,3498,3499,3702,3708,3760,3854,3943,4063,4390,4674,4699,4737,4797,4803,4827,4833,4926,4943,4945,4968,5336,5339,5365,5707,
5743,5793,5806,5903,5905,5921,5925,5938,6028,6043,6047,6049,6057,6131,6140,6173,6183,6192,6286,6298,6304,6338,6498,6508,6539,6650,
6723,6737,6744,6764,6799,6836,6851,6854,6896,6919,6947,7085,7187,7218,7293,7330,7386,7453,7519,7556,7562,7616,7620,7624,7632,7647,
7661,7662,7682,7817,7850,7872,7927,8036,8051,8052,8078,8152,8172,8336,8357,8453,8459,8492,8498,8560,8573,8666,8673,8746,8751,8768,
8773,9054,9058,9081,9097,9126,9131,9151,9197,9212,9273,9308,9310,9330,9342,9376,9390,9416,9432,9454,9475,9535,9548,9570,9573,9576,
9578,9587,9609,9620,9621,9637,9655,9656,9664,9680,9690,9715,9732,9734,9736,9804,9932,283,377,446,557,559,565,639,849,851,
866,872,994,2946,3683,3761,3776,3803,3899,3983,4095,4605,4695,4738,4842,4986,5036,5039,5076,5146,5394,5406,5538,5933,5980,5993,
6054,6077,6087,6091,6385,6391,6490,6529,6637,6683,6704,6749,6760,6813,6904,6940,6964,7026,7054,7136,7167,7192,7336,7354,7365,7462,
7538,7668,7935,8035,8131,8167,8295,8313,8355,8359,8363,8396,8435,8447,8449,8467,8594,8656,8679,8705,8748,8760,8792,8927,9084,9244,
9253,9261,9268,9276,9297,9304,9326,9329,9337,9350,9378,9418,9457,9459,9472,9473,9483,9488,9581,9596,9694,9755,9762,9772,9778,9827,
9843,9850,9863,9946,9974,259,293,299,340,390,460,498,681,795,975,3749,3896,3904,3906,3964,3998,4056,4493,4629,4696,4965,
5084,5093,5195,5393,5398,5936,5947,5972,5992,6013,6018,6026,6075,6089,6197,6296,6359,6396,6528,6560,6729,6816,6846,6850,6857,6893,
6939,7032,7049,7345,7348,7443,7599,7835,7939,7944,7949,7996,8045,8047,8058,8063,8149,8268,8276,8296,8365,8553,8592,8781,8783,8940,
8982,9065,9129,9136,9167,9217,9240,9282,9320,9344,9362,9429,9467,9492,9509,9543,9589,9592,9593,9668,9817,9858,95,266,298,380,
392,538,548,596,597,671,693,745,751,756,768,843,860,894,949,3660,3752,3754,3872,3903,3907,3929,3955,3967,3986,4048,
4081,4703,4963,4996,5094,5209,5929,6055,6138,6142,6247,6343,6382,6390,6403,6734,6831,6949,7084,7097,7141,7169,7438,7552,7593,7730,
7937,7947,8194,8229,8270,8326,8354,8551,8628,8635,8647,8652,8717,8744,8837,8849,8935,8962,9043,9143,9186,9307,9334,9374,9379,9382,
9402,9406,9489,9534,9616,9650,9740,9835,9862,384,438,480,646,651,674,679,736,766,845,853,964,3049,3076,3086,3796,3934,
4093,4097,4764,4927,4930,4970,5068,5099,5196,5328,5373,5389,5497,5956,6041,6076,6182,6306,6307,6434,6905,6927,6929,7038,7046,7148,
7434,7435,7450,7460,7495,7554,7652,7695,7740,7843,8048,8064,8329,8364,8374,8496,8548,8634,8680,8714,8718,8953,8995,9033,9035,9236,
9245,9360,9375,9415,9434,9435,9436,9477,9626,9643,9673,9730,9748,9768,9857,9906,9948,146,261,294,374,381,496,499,575,643,
735,784,836,842,855,960,2894,3046,3063,3768,3772,3950,3980,4037,4064,4073,4079,4309,4634,4730,4839,4928,5086,5376,5838,5948,
5994,5996,6085,6137,6167,6194,6237,6440,6695,6720,6738,6804,6826,6856,6862,6935,6937,7043,7064,7340,7362,7549,7629,7967,8072,8174,
8259,8443,8493,8619,8643,8735,8736,8776,8795,8941,8983,9032,9034,9046,9108,9206,9289,9313,9352,9353,9358,9380,9385,9386,9445,9468,
9564,9607,9617,9702,9743,9833,389,393,443,492,595,743,749,762,3091,3809,3873,3898,3932,4704,5097,5729,5749,6038,6052,6053,
6072,6139,6495,6594,6727,6748,6792,6818,6823,7037,7370,7493,7618,7683,7834,7994,8041,8043,8362,8568,8653,8697,8725,8747,8794,8960,
9130,9183,9241,9246,9257,9384,9549,9572,9728,9769,9816,9892,9928,292,362,436,659,947,961,5073,5549,5935,5982,6058,6193,6394,
7346,7358,7360,7396,7439,7597,7930,7990,8097,8278,8395,9049,9249,9287,9407,9446,9624,9893,9926,296,537,692,760,3093,4085,4305,
4603,4604,4618,4962,5726,5817,5934,6071,6086,6229,6346,6408,6438,6573,6735,6736,7041,7059,7194,7196,7350,7628,7948,8294,8339,8349,
8394,8903,8952,9036,9063,9085,9107,9139,9141,9269,9351,9433,9640,9679,9846,9861,670,673,839,2493,4392,4904,6303,6706,6807,8057,
8074,8578,8638,8739,8829,8926,8961,9048,9066,9174,9207,9209,9228,9419,9574,9670,544,589,672,767,940,5706,6073,6376,6384,6439,
6538,6732,6763,6817,6843,6853,7052,7149,7635,7639,7698,7838,8061,8344,8637,8743,9037,9149,9205,9208,9302,9361,9538,9615,9645,9682,
9735,9759,696,4083,4905,6056,6092,6863,7056,7461,7636,7830,7962,8059,8095,8737,9305,9364,9409,9528,9703,9839,447,4940,5194,6079,
6084,6094,6492,6724,6805,6906,7061,7094,7339,7938,8334,8376,8620,8641,9051,9068,9073,9185,9370,9482,9647,9681,9683,593,647,746,
793,3951,4761,6059,6078,6328,6629,6829,8039,8092,8429,8839,8947,9038,9064,9178,9359,9367,9381,9391,9447,9460,9628,9660,9726,9729,
856,3953,6097,6726,7091,8076,8728,9469,9529,9608,9940,763,847,4934,5928,6095,6297,6496,8346,8356,8538,8598,8729,8738,8936,8939,
9265,9343,9347,9737,794,6096,7638,8067,8973,9340,9373,9550,6098,6803,6994,7436,8636,9430,635,6039,7036,7349,7693,8065,8137,8437,
8948,9138,9938,675,9071,9076,9148,9159,9526,3794,6082,7065,8397,8539,8646,9695,9805,6806,7993,8146,8343,8557,439,8438,9047,9539,
6093,7063,8196,6827,7394,859,8957,9480,6793,738,8398,6835,7637,9629,8093,8068
};

// Initialize components
dscKeybusInterface dsc(dscClockPin, dscReadPin, dscWritePin);
int testCode = 0;
char testCodeChar[5];
int codeListCount = sizeof(codeList) / sizeof(codeList[0]);
int codeListCounter = startPosition;
bool pauseTest = false;
byte testCount = 1;
byte lockoutThreshold;


void setup() {
  Serial.begin(115200);
  delay(1000);
  Serial.println();
  Serial.println();

  // Pin setup
  pinMode(LED_BUILTIN, OUTPUT);
  digitalWrite(LED_BUILTIN, HIGH);
  pinMode(dscRelayPin, OUTPUT);
  digitalWrite(dscRelayPin, LOW);

  // Starts the Keybus interface and optionally specifies how to print data.
  // begin() sets Serial by default and can accept a different stream: begin(Serial1), etc.
  dsc.begin();
  Serial.print(F("DSC Keybus Interface...."));

  // Loops until partition 1 is ready for key presses in status "Partition ready" (0x01),
  // "Stay/away zones open" (0x02), or "Zones open" (0x03)
  while (!dsc.status[0] || dsc.status[0] > 0x03) dsc.loop();
  Serial.println(F("connected."));
}


void loop() {

  // Checks if the interface is connected to the Keybus
  if (dsc.keybusChanged) {
    dsc.keybusChanged = false;  // Resets the Keybus data status flag
    if (!dsc.keybusConnected) {
      Serial.println(F("Keybus disconnected"));
      return;
    }
  }

  // Checks for serial input to pause/resume the code search if any key is sent
  if (Serial.available() > 0) {
    char c = Serial.read();
    if (c >= 32) {  // Checks for typical keyboard ASCII characters
      if (pauseTest) {
        pauseTest = false;
        printTimestamp();
        Serial.println("Resuming code search");
        while (dsc.status[0] != 0x01 && dsc.status[0] != 0x02 && dsc.status[0] != 0x03) dsc.loop();
      }
      else {
        pauseTest = true;
        printTimestamp();
        dsc.write('#');
        Serial.println("Paused code search");
      }
    }
  }
  if (pauseTest) return;

  // Sets the test code from the code list
  if (codeListCounter < codeListCount) {
    testCode = codeList[codeListCounter];
    codeListCounter++;
  }
  else {
    Serial.println("All codes tested, no results.");
    while(true) yield();
  }

  // Loops until the partition 1 status is "Partition ready" (0x01), "Stay/away zones open" (0x02),
  // "Zones open" (0x03), or "Enter installer code" (0xB7)
  while (dsc.status[0] != 0x01 && dsc.status[0] != 0x02 && dsc.status[0] != 0x03 && dsc.status[0] != 0xB7) dsc.loop();

  // Skips keypad lockout if an access code is available to arm/disarm the panel
  if (testCount == lockoutThreshold && strlen(accessCode)) {
    testCount = 1;
    dsc.write('#');                                                     // Exit "Enter installer code" prompt
    while (dsc.status[0] != 0x01 && dsc.status[0] != 0x02) dsc.loop();  // Loop until the partition is ready
    dsc.write('s');                                                     // Stay arm
    while (dsc.status[0] != 0x08 && dsc.status[0] != 0x9F) dsc.loop();  // Loop until "Exit delay" or "Enter access code"
    if (dsc.status[0] == 0x9F) {
      dsc.write(accessCode);                                            // Enters the access code to arm if required
    }
    while (dsc.status[0] != 0x08) dsc.loop();                           // Loop until "Exit delay"
    dsc.write(accessCode);                                              // Enters the access code to disarm
    while (dsc.status[0] != 0x01 && dsc.status[0] != 0x02 && dsc.status[0] != 0x3E) dsc.loop();  // Loop until the partition is ready
  }

  // Enters installer programming mode
  if (dsc.status[0] == 0x01 || dsc.status[0] == 0x02 || dsc.status[0] == 0x03 || dsc.status[0] == 0x3E) {
    dsc.write("*8");
    while (dsc.status[0] != 0xB7) dsc.loop();  // Loop until "Enter installer code" (0xB7)
  }

  // Enters the test code on "Enter installer code"
  if (dsc.status[0] == 0xB7) {
    printTimestamp();
    Serial.print("Test position: ");
    Serial.print(codeListCounter - 1);
    Serial.print(" | Test code: ");
    itoa(testCode, testCodeChar, 10);
    if (testCode < 10) {
      Serial.print("000");
      Serial.println(testCode);
      dsc.write("000");
      dsc.write(testCodeChar);
    }
    else if (testCode < 100) {
      Serial.print("00");
      Serial.println(testCode);
      dsc.write("00");
      dsc.write(testCodeChar);
    }
    else if (testCode < 1000) {
      Serial.print("0");
      Serial.println(testCode);
      dsc.write('0');
      dsc.write(testCodeChar);
    }
    else {
      Serial.println(testCode);
      dsc.write(testCodeChar);
    }

    // Loops until "Keypad lockout" (0x10), "Invalid access code" (0x8F), or "*8 Main Menu" (0xE4)
    while (dsc.status[0] != 0x10 && dsc.status[0] != 0x8F && dsc.status[0] != 0xE4) dsc.loop();

    // Keypad lockout
    if (dsc.status[0] == 0x10) {
      lockoutThreshold = testCount;
      testCount = 1;
      printTimestamp();
      Serial.println("Keypad lockout");

      // Cycles the optional relay
      digitalWrite(dscRelayPin, HIGH);
      delay(1000);
      digitalWrite(dscRelayPin, LOW);

      // Loops until the lockout expires
      while (dsc.status[0] == 0x10) dsc.loop();
    }

    // Invalid access code - loops until "Enter installer code" (0xB7)
    else if (dsc.status[0] == 0x8F) {
      while (dsc.status[0] != 0xB7) dsc.loop();
      testCount++;
    }

    // *8 Main Menu
    else if (dsc.status[0] == 0xE4) {

      // Attempts to enter keypad programming to check if code is valid for programming
      dsc.write('0');
      dsc.write('0');
      dsc.write('0');

      // Loops until the panel sends a status command (0x05) or a long beep command (0x7F)
      while (dsc.panelData[0] != 0x05 && dsc.panelData[0] != 0x7F) dsc.loop();

      // Long beep, code is not valid for programming
      if (dsc.panelData[0] == 0x7F) {
        printTimestamp();
        Serial.print("Non-programming *8 code: ");
        Serial.println(testCode);
        dsc.write('#');
        testCount++;
      }

      // Entered keypad programming, code is valid - exits the installer menu and outputs the code via serial and LED blinking
      else if (dsc.status[0] == 0xF8) {
        printTimestamp();
        Serial.print("Installer code: ");
        Serial.println(testCode);
        dsc.write('#');
        dsc.write('#');

        // Blinks the LED - each digit is indicated by the number of blinks, a long blink indicates "0".
        while(true) {
          byte leadingZeros = 0;
          byte leadingZerosTotal = 0;
          if (testCode < 10) {
            leadingZeros = 3;
            leadingZerosTotal = 3;
          }
          else if (testCode < 100) {
            leadingZeros = 2;
            leadingZerosTotal = 2;
          }
          else if (testCode < 1000) {
            leadingZeros = 1;
            leadingZerosTotal = 1;
          }
          for (byte digit = 0; digit < 4; digit++) {
            byte blinks;
            if (leadingZeros > 0) {
              blinks = 0;
              leadingZeros--;
            }
            else blinks = testCodeChar[digit - leadingZerosTotal] - 48;

            if (blinks == 0) {
              digitalWrite(LED_BUILTIN, LOW);
              delay(750);
              digitalWrite(LED_BUILTIN, HIGH);
              delay(400);
            }
            else {
              for (byte i = 0; i < blinks; i++) {
                digitalWrite(LED_BUILTIN, LOW);
                delay(100);
                digitalWrite(LED_BUILTIN, HIGH);
                delay(400);
              }
            }
            delay(1000);
          }
          delay(3000);
        }
      }
    }
  }
}


// Prints a timestamp in seconds
void printTimestamp() {
  unsigned long timeStamp = millis() / 1000;
  if (timeStamp < 10) Serial.print("    ");
  else if (timeStamp < 100) Serial.print("   ");
  else if (timeStamp < 1000) Serial.print("  ");
  else if (timeStamp < 10000) Serial.print(" ");
  Serial.print(timeStamp);
  Serial.print(F("s | "));
}