# coding=utf8
# the above tag defines encoding for this document and is for Python 2.x compatibility
import re
regex = r"^(?)[0-9]?)$)(?:([0-9]*)(?:0\N*(?=\n\N+\n\N+\n\2[1-9])|1\N*(?=\n\N+\n\N+\n\2[2-9])|2\N*(?=\n\N+\n\N+\n\2[3-9])|3\N*(?=\n\N+\n\N+\n\2[4-9])|4\N*(?=\n\N+\n\N+\n\2[5-9])|5\N*(?=\n\N+\n\N+\n\2[6-9])|6\N*(?=\n\N+\n\N+\n\2[7-9])|7\N*(?=\n\N+\n\N+\n\2[89])|8\N*(?=\n\N+\n\N+\n\2[9]))|(?=([0-9](?:\n\N+\n\N+\n|(?-1))[0-9])[0-9]))"
test_str = ("143\n"
"147\n"
"150\n"
"166\n"
"180\n"
"187\n"
"188\n"
"185\n"
"199\n"
"198\n"
"199\n"
"197\n"
"218\n"
"221\n"
"238\n"
"239\n"
"233\n"
"234\n"
"217\n"
"212\n"
"215\n"
"216\n"
"215\n"
"217\n"
"220\n"
"241\n"
"245\n"
"232\n"
"230\n"
"234\n"
"206\n"
"251\n"
"272\n"
"273\n"
"278\n"
"279\n"
"285\n"
"292\n"
"288\n"
"286\n"
"289\n"
"290\n"
"294\n"
"301\n"
"298\n"
"300\n"
"297\n"
"305\n"
"306\n"
"310\n"
"340\n"
"343\n"
"352\n"
"356\n"
"362\n"
"376\n"
"380\n"
"383\n"
"382\n"
"385\n"
"372\n"
"391\n"
"384\n"
"385\n"
"398\n"
"430\n"
"426\n"
"422\n"
"423\n"
"433\n"
"419\n"
"421\n"
"431\n"
"424\n"
"442\n"
"450\n"
"453\n"
"449\n"
"487\n"
"491\n"
"462\n"
"464\n"
"466\n"
"467\n"
"468\n"
"466\n"
"482\n"
"484\n"
"501\n"
"500\n"
"501\n"
"497\n"
"498\n"
"497\n"
"508\n"
"516\n"
"521\n"
"540\n"
"541\n"
"536\n"
"537\n"
"536\n"
"542\n"
"549\n"
"535\n"
"541\n"
"548\n"
"549\n"
"551\n"
"570\n"
"572\n"
"606\n"
"605\n"
"601\n"
"608\n"
"609\n"
"611\n"
"605\n"
"631\n"
"618\n"
"635\n"
"636\n"
"635\n"
"636\n"
"637\n"
"638\n"
"676\n"
"673\n"
"668\n"
"674\n"
"683\n"
"684\n"
"683\n"
"680\n"
"687\n"
"688\n"
"698\n"
"700\n"
"706\n"
"696\n"
"713\n"
"707\n"
"708\n"
"719\n"
"721\n"
"728\n"
"719\n"
"723\n"
"715\n"
"712\n"
"722\n"
"721\n"
"709\n"
"680\n"
"681\n"
"680\n"
"681\n"
"690\n"
"686\n"
"687\n"
"682\n"
"683\n"
"680\n"
"693\n"
"708\n"
"718\n"
"730\n"
"743\n"
"726\n"
"753\n"
"747\n"
"748\n"
"751\n"
"772\n"
"801\n"
"805\n"
"797\n"
"789\n"
"790\n"
"797\n"
"812\n"
"806\n"
"813\n"
"815\n"
"813\n"
"815\n"
"822\n"
"835\n"
"843\n"
"854\n"
"858\n"
"859\n"
"860\n"
"869\n"
"872\n"
"870\n"
"864\n"
"876\n"
"880\n"
"882\n"
"865\n"
"869\n"
"876\n"
"882\n"
"886\n"
"885\n"
"898\n"
"900\n"
"909\n"
"913\n"
"902\n"
"910\n"
"914\n"
"916\n"
"920\n"
"898\n"
"899\n"
"931\n"
"936\n"
"937\n"
"938\n"
"941\n"
"950\n"
"939\n"
"942\n"
"935\n"
"932\n"
"941\n"
"945\n"
"944\n"
"957\n"
"959\n"
"967\n"
"975\n"
"990\n"
"1011\n"
"1008\n"
"1011\n"
"1015\n"
"1017\n"
"1018\n"
"1011\n"
"1010\n"
"1035\n"
"1036\n"
"1040\n"
"1041\n"
"1046\n"
"1048\n"
"1027\n"
"1047\n"
"1069\n"
"1079\n"
"1074\n"
"1075\n"
"1080\n"
"1079\n"
"1083\n"
"1071\n"
"1077\n"
"1080\n"
"1081\n"
"1082\n"
"1083\n"
"1085\n"
"1087\n"
"1089\n"
"1095\n"
"1096\n"
"1099\n"
"1110\n"
"1112\n"
"1119\n"
"1122\n"
"1124\n"
"1130\n"
"1133\n"
"1143\n"
"1139\n"
"1141\n"
"1142\n"
"1144\n"
"1176\n"
"1175\n"
"1159\n"
"1165\n"
"1172\n"
"1182\n"
"1203\n"
"1209\n"
"1193\n"
"1194\n"
"1193\n"
"1191\n"
"1196\n"
"1201\n"
"1202\n"
"1205\n"
"1216\n"
"1219\n"
"1220\n"
"1213\n"
"1212\n"
"1220\n"
"1226\n"
"1233\n"
"1234\n"
"1236\n"
"1239\n"
"1240\n"
"1242\n"
"1237\n"
"1261\n"
"1259\n"
"1257\n"
"1245\n"
"1251\n"
"1252\n"
"1272\n"
"1276\n"
"1277\n"
"1279\n"
"1284\n"
"1285\n"
"1286\n"
"1285\n"
"1315\n"
"1316\n"
"1331\n"
"1333\n"
"1335\n"
"1347\n"
"1344\n"
"1343\n"
"1342\n"
"1340\n"
"1354\n"
"1359\n"
"1367\n"
"1368\n"
"1378\n"
"1380\n"
"1358\n"
"1370\n"
"1371\n"
"1387\n"
"1388\n"
"1402\n"
"1404\n"
"1406\n"
"1401\n"
"1403\n"
"1405\n"
"1407\n"
"1408\n"
"1428\n"
"1432\n"
"1433\n"
"1434\n"
"1435\n"
"1446\n"
"1460\n"
"1461\n"
"1460\n"
"1468\n"
"1471\n"
"1472\n"
"1474\n"
"1465\n"
"1473\n"
"1496\n"
"1507\n"
"1510\n"
"1506\n"
"1502\n"
"1509\n"
"1512\n"
"1515\n"
"1516\n"
"1524\n"
"1526\n"
"1527\n"
"1528\n"
"1527\n"
"1541\n"
"1544\n"
"1545\n"
"1543\n"
"1548\n"
"1551\n"
"1544\n"
"1545\n"
"1550\n"
"1554\n"
"1556\n"
"1557\n"
"1558\n"
"1575\n"
"1578\n"
"1581\n"
"1587\n"
"1586\n"
"1590\n"
"1584\n"
"1571\n"
"1576\n"
"1574\n"
"1575\n"
"1585\n"
"1601\n"
"1604\n"
"1612\n"
"1613\n"
"1600\n"
"1587\n"
"1591\n"
"1596\n"
"1595\n"
"1601\n"
"1608\n"
"1614\n"
"1615\n"
"1614\n"
"1634\n"
"1636\n"
"1637\n"
"1639\n"
"1642\n"
"1629\n"
"1617\n"
"1618\n"
"1617\n"
"1612\n"
"1613\n"
"1614\n"
"1615\n"
"1617\n"
"1608\n"
"1609\n"
"1611\n"
"1608\n"
"1634\n"
"1636\n"
"1641\n"
"1637\n"
"1657\n"
"1665\n"
"1668\n"
"1679\n"
"1680\n"
"1695\n"
"1697\n"
"1698\n"
"1669\n"
"1670\n"
"1669\n"
"1673\n"
"1672\n"
"1678\n"
"1670\n"
"1671\n"
"1673\n"
"1689\n"
"1683\n"
"1685\n"
"1691\n"
"1692\n"
"1669\n"
"1670\n"
"1679\n"
"1672\n"
"1684\n"
"1704\n"
"1700\n"
"1692\n"
"1714\n"
"1715\n"
"1716\n"
"1712\n"
"1714\n"
"1716\n"
"1714\n"
"1718\n"
"1719\n"
"1713\n"
"1717\n"
"1710\n"
"1711\n"
"1721\n"
"1745\n"
"1752\n"
"1767\n"
"1762\n"
"1787\n"
"1785\n"
"1786\n"
"1790\n"
"1796\n"
"1814\n"
"1843\n"
"1859\n"
"1871\n"
"1876\n"
"1890\n"
"1891\n"
"1892\n"
"1894\n"
"1912\n"
"1914\n"
"1939\n"
"1955\n"
"1956\n"
"1960\n"
"1964\n"
"1967\n"
"1970\n"
"1971\n"
"1972\n"
"1969\n"
"1970\n"
"1984\n"
"1996\n"
"2017\n"
"2018\n"
"2020\n"
"2005\n"
"2006\n"
"2005\n"
"2007\n"
"2005\n"
"2006\n"
"2027\n"
"2031\n"
"2032\n"
"2012\n"
"2014\n"
"2013\n"
"2016\n"
"2014\n"
"2018\n"
"2040\n"
"2042\n"
"2061\n"
"2064\n"
"2063\n"
"2080\n"
"2086\n"
"2094\n"
"2063\n"
"2071\n"
"2092\n"
"2077\n"
"2078\n"
"2079\n"
"2080\n"
"2099\n"
"2100\n"
"2103\n"
"2118\n"
"2119\n"
"2124\n"
"2128\n"
"2135\n"
"2136\n"
"2135\n"
"2136\n"
"2137\n"
"2135\n"
"2163\n"
"2168\n"
"2162\n"
"2164\n"
"2160\n"
"2161\n"
"2162\n"
"2165\n"
"2169\n"
"2168\n"
"2185\n"
"2191\n"
"2197\n"
"2212\n"
"2224\n"
"2228\n"
"2229\n"
"2230\n"
"2243\n"
"2250\n"
"2251\n"
"2252\n"
"2255\n"
"2256\n"
"2247\n"
"2253\n"
"2262\n"
"2296\n"
"2317\n"
"2324\n"
"2327\n"
"2299\n"
"2300\n"
"2290\n"
"2291\n"
"2303\n"
"2292\n"
"2293\n"
"2294\n"
"2297\n"
"2298\n"
"2308\n"
"2309\n"
"2312\n"
"2337\n"
"2340\n"
"2349\n"
"2354\n"
"2345\n"
"2341\n"
"2340\n"
"2341\n"
"2344\n"
"2345\n"
"2341\n"
"2346\n"
"2352\n"
"2357\n"
"2340\n"
"2339\n"
"2336\n"
"2339\n"
"2351\n"
"2356\n"
"2358\n"
"2364\n"
"2366\n"
"2367\n"
"2370\n"
"2376\n"
"2377\n"
"2375\n"
"2378\n"
"2391\n"
"2394\n"
"2389\n"
"2391\n"
"2388\n"
"2389\n"
"2407\n"
"2420\n"
"2417\n"
"2416\n"
"2424\n"
"2443\n"
"2455\n"
"2457\n"
"2446\n"
"2449\n"
"2458\n"
"2466\n"
"2479\n"
"2486\n"
"2478\n"
"2491\n"
"2503\n"
"2507\n"
"2513\n"
"2518\n"
"2500\n"
"2502\n"
"2504\n"
"2514\n"
"2516\n"
"2517\n"
"2518\n"
"2529\n"
"2532\n"
"2543\n"
"2544\n"
"2543\n"
"2545\n"
"2553\n"
"2548\n"
"2559\n"
"2563\n"
"2573\n"
"2587\n"
"2584\n"
"2581\n"
"2579\n"
"2582\n"
"2577\n"
"2588\n"
"2589\n"
"2614\n"
"2617\n"
"2620\n"
"2622\n"
"2615\n"
"2619\n"
"2618\n"
"2610\n"
"2616\n"
"2615\n"
"2618\n"
"2616\n"
"2627\n"
"2630\n"
"2641\n"
"2659\n"
"2662\n"
"2663\n"
"2661\n"
"2669\n"
"2662\n"
"2687\n"
"2690\n"
"2691\n"
"2693\n"
"2696\n"
"2728\n"
"2746\n"
"2743\n"
"2746\n"
"2745\n"
"2746\n"
"2742\n"
"2749\n"
"2756\n"
"2750\n"
"2738\n"
"2743\n"
"2744\n"
"2746\n"
"2750\n"
"2753\n"
"2762\n"
"2770\n"
"2767\n"
"2766\n"
"2778\n"
"2780\n"
"2781\n"
"2776\n"
"2763\n"
"2762\n"
"2763\n"
"2766\n"
"2762\n"
"2753\n"
"2761\n"
"2768\n"
"2772\n"
"2746\n"
"2762\n"
"2767\n"
"2774\n"
"2795\n"
"2806\n"
"2809\n"
"2816\n"
"2830\n"
"2821\n"
"2837\n"
"2836\n"
"2838\n"
"2842\n"
"2831\n"
"2815\n"
"2816\n"
"2818\n"
"2817\n"
"2822\n"
"2817\n"
"2823\n"
"2834\n"
"2825\n"
"2818\n"
"2821\n"
"2847\n"
"2846\n"
"2845\n"
"2847\n"
"2848\n"
"2849\n"
"2863\n"
"2872\n"
"2866\n"
"2874\n"
"2875\n"
"2885\n"
"2886\n"
"2892\n"
"2898\n"
"2897\n"
"2917\n"
"2922\n"
"2916\n"
"2921\n"
"2922\n"
"2921\n"
"2940\n"
"2945\n"
"2935\n"
"2950\n"
"2946\n"
"2949\n"
"2951\n"
"2948\n"
"2940\n"
"2941\n"
"2940\n"
"2939\n"
"2955\n"
"2943\n"
"2941\n"
"2942\n"
"2945\n"
"2961\n"
"2962\n"
"2965\n"
"2975\n"
"2970\n"
"2971\n"
"2960\n"
"2961\n"
"2956\n"
"2960\n"
"2961\n"
"2967\n"
"2966\n"
"2979\n"
"2976\n"
"2983\n"
"3012\n"
"3024\n"
"3021\n"
"3041\n"
"3040\n"
"3041\n"
"3042\n"
"3048\n"
"3077\n"
"3088\n"
"3091\n"
"3109\n"
"3107\n"
"3116\n"
"3111\n"
"3115\n"
"3121\n"
"3095\n"
"3097\n"
"3077\n"
"3059\n"
"3065\n"
"3068\n"
"3061\n"
"3062\n"
"3061\n"
"3063\n"
"3068\n"
"3070\n"
"3073\n"
"3057\n"
"3075\n"
"3082\n"
"3089\n"
"3086\n"
"3090\n"
"3092\n"
"3106\n"
"3112\n"
"3118\n"
"3120\n"
"3119\n"
"3121\n"
"3119\n"
"3126\n"
"3133\n"
"3135\n"
"3163\n"
"3166\n"
"3167\n"
"3181\n"
"3185\n"
"3191\n"
"3197\n"
"3198\n"
"3199\n"
"3194\n"
"3210\n"
"3216\n"
"3224\n"
"3225\n"
"3235\n"
"3237\n"
"3245\n"
"3253\n"
"3259\n"
"3248\n"
"3256\n"
"3273\n"
"3265\n"
"3248\n"
"3249\n"
"3258\n"
"3257\n"
"3256\n"
"3255\n"
"3250\n"
"3252\n"
"3260\n"
"3261\n"
"3267\n"
"3268\n"
"3269\n"
"3284\n"
"3294\n"
"3334\n"
"3337\n"
"3340\n"
"3307\n"
"3316\n"
"3320\n"
"3328\n"
"3330\n"
"3350\n"
"3357\n"
"3363\n"
"3364\n"
"3361\n"
"3396\n"
"3397\n"
"3410\n"
"3411\n"
"3433\n"
"3452\n"
"3453\n"
"3465\n"
"3467\n"
"3469\n"
"3470\n"
"3467\n"
"3480\n"
"3494\n"
"3517\n"
"3519\n"
"3527\n"
"3542\n"
"3546\n"
"3547\n"
"3544\n"
"3570\n"
"3571\n"
"3596\n"
"3604\n"
"3603\n"
"3587\n"
"3588\n"
"3591\n"
"3589\n"
"3590\n"
"3591\n"
"3600\n"
"3598\n"
"3599\n"
"3600\n"
"3599\n"
"3600\n"
"3609\n"
"3608\n"
"3610\n"
"3611\n"
"3632\n"
"3633\n"
"3632\n"
"3633\n"
"3635\n"
"3642\n"
"3643\n"
"3656\n"
"3652\n"
"3653\n"
"3657\n"
"3676\n"
"3677\n"
"3687\n"
"3690\n"
"3693\n"
"3694\n"
"3697\n"
"3702\n"
"3703\n"
"3722\n"
"3729\n"
"3730\n"
"3731\n"
"3737\n"
"3744\n"
"3747\n"
"3751\n"
"3757\n"
"3758\n"
"3761\n"
"3769\n"
"3781\n"
"3796\n"
"3798\n"
"3797\n"
"3798\n"
"3812\n"
"3848\n"
"3849\n"
"3850\n"
"3854\n"
"3861\n"
"3859\n"
"3863\n"
"3867\n"
"3870\n"
"3882\n"
"3884\n"
"3876\n"
"3879\n"
"3909\n"
"3908\n"
"3910\n"
"3909\n"
"3908\n"
"3886\n"
"3888\n"
"3889\n"
"3891\n"
"3920\n"
"3921\n"
"3922\n"
"3913\n"
"3955\n"
"3956\n"
"3974\n"
"3975\n"
"3976\n"
"3988\n"
"3992\n"
"3999\n"
"4009\n"
"4010\n"
"4019\n"
"4023\n"
"4024\n"
"4035\n"
"4045\n"
"4044\n"
"4046\n"
"4072\n"
"4074\n"
"4093\n"
"4101\n"
"4105\n"
"4111\n"
"4141\n"
"4146\n"
"4147\n"
"4160\n"
"4162\n"
"4161\n"
"4162\n"
"4156\n"
"4158\n"
"4160\n"
"4168\n"
"4169\n"
"4168\n"
"4169\n"
"4192\n"
"4191\n"
"4222\n"
"4239\n"
"4227\n"
"4228\n"
"4226\n"
"4228\n"
"4227\n"
"4228\n"
"4221\n"
"4222\n"
"4223\n"
"4248\n"
"4249\n"
"4258\n"
"4249\n"
"4257\n"
"4260\n"
"4258\n"
"4257\n"
"4259\n"
"4260\n"
"4267\n"
"4284\n"
"4285\n"
"4286\n"
"4283\n"
"4280\n"
"4281\n"
"4280\n"
"4279\n"
"4282\n"
"4289\n"
"4290\n"
"4295\n"
"4300\n"
"4289\n"
"4290\n"
"4291\n"
"4300\n"
"4310\n"
"4314\n"
"4319\n"
"4320\n"
"4321\n"
"4324\n"
"4330\n"
"4326\n"
"4340\n"
"4326\n"
"4327\n"
"4332\n"
"4333\n"
"4334\n"
"4339\n"
"4361\n"
"4369\n"
"4370\n"
"4374\n"
"4372\n"
"4382\n"
"4398\n"
"4399\n"
"4395\n"
"4396\n"
"4397\n"
"4400\n"
"4404\n"
"4401\n"
"4405\n"
"4415\n"
"4427\n"
"4433\n"
"4446\n"
"4447\n"
"4455\n"
"4456\n"
"4457\n"
"4458\n"
"4467\n"
"4471\n"
"4463\n"
"4470\n"
"4460\n"
"4458\n"
"4459\n"
"4457\n"
"4468\n"
"4470\n"
"4448\n"
"4449\n"
"4453\n"
"4474\n"
"4470\n"
"4475\n"
"4474\n"
"4473\n"
"4472\n"
"4474\n"
"4476\n"
"4478\n"
"4479\n"
"4483\n"
"4484\n"
"4485\n"
"4481\n"
"4483\n"
"4492\n"
"4505\n"
"4513\n"
"4529\n"
"4530\n"
"4531\n"
"4503\n"
"4504\n"
"4505\n"
"4499\n"
"4500\n"
"4516\n"
"4517\n"
"4513\n"
"4497\n"
"4493\n"
"4494\n"
"4524\n"
"4537\n"
"4543\n"
"4544\n"
"4551\n"
"4552\n"
"4555\n"
"4565\n"
"4567\n"
"4566\n"
"4567\n"
"4566\n"
"4590\n"
"4591\n"
"4596\n"
"4597\n"
"4588\n"
"4572\n"
"4575\n"
"4572\n"
"4574\n"
"4575\n"
"4576\n"
"4584\n"
"4572\n"
"4578\n"
"4579\n"
"4593\n"
"4600\n"
"4604\n"
"4584\n"
"4586\n"
"4583\n"
"4599\n"
"4601\n"
"4603\n"
"4625\n"
"4624\n"
"4625\n"
"4627\n"
"4623\n"
"4624\n"
"4620\n"
"4618\n"
"4617\n"
"4616\n"
"4617\n"
"4612\n"
"4623\n"
"4634\n"
"4635\n"
"4623\n"
"4628\n"
"4629\n"
"4631\n"
"4633\n"
"4654\n"
"4659\n"
"4669\n"
"4674\n"
"4677\n"
"4678\n"
"4694\n"
"4699\n"
"4701\n"
"4713\n"
"4714\n"
"4722\n"
"4724\n"
"4725\n"
"4761\n"
"4785\n"
"4791\n"
"4783\n"
"4790\n"
"4791\n"
"4792\n"
"4809\n"
"4835\n"
"4840\n"
"4845\n"
"4852\n"
"4851\n"
"4852\n"
"4846\n"
"4848\n"
"4849\n"
"4854\n"
"4856\n"
"4862\n"
"4856\n"
"4875\n"
"4876\n"
"4878\n"
"4892\n"
"4893\n"
"4903\n"
"4891\n"
"4909\n"
"4923\n"
"4938\n"
"4939\n"
"4944\n"
"4953\n"
"4954\n"
"4975\n"
"4977\n"
"4978\n"
"4984\n"
"4987\n"
"4989\n"
"4987\n"
"4995\n"
"4994\n"
"4996\n"
"5000\n"
"5008\n"
"5018\n"
"5024\n"
"5027\n"
"5028\n"
"5031\n"
"5035\n"
"5051\n"
"5059\n"
"5061\n"
"5065\n"
"5069\n"
"5090\n"
"5110\n"
"5111\n"
"5113\n"
"5115\n"
"5129\n"
"5128\n"
"5139\n"
"5140\n"
"5141\n"
"5142\n"
"5149\n"
"5148\n"
"5147\n"
"5153\n"
"5157\n"
"5178\n"
"5189\n"
"5209\n"
"5217\n"
"5211\n"
"5215\n"
"5221\n"
"5243\n"
"5244\n"
"5275\n"
"5287\n"
"5290\n"
"5300\n"
"5301\n"
"5297\n"
"5300\n"
"5289\n"
"5311\n"
"5314\n"
"5303\n"
"5304\n"
"5306\n"
"5307\n"
"5316\n"
"5329\n"
"5330\n"
"5333\n"
"5334\n"
"5335\n"
"5343\n"
"5359\n"
"5380\n"
"5382\n"
"5383\n"
"5392\n"
"5403\n"
"5409\n"
"5410\n"
"5420\n"
"5427\n"
"5438\n"
"5448\n"
"5455\n"
"5458\n"
"5489\n"
"5490\n"
"5491\n"
"5492\n"
"5494\n"
"5497\n"
"5522\n"
"5523\n"
"5525\n"
"5536\n"
"5537\n"
"5542\n"
"5522\n"
"5529\n"
"5534\n"
"5535\n"
"5545\n"
"5546\n"
"5544\n"
"5538\n"
"5547\n"
"5551\n"
"5550\n"
"5551\n"
"5552\n"
"5553\n"
"5565\n"
"5578\n"
"5589\n"
"5590\n"
"5589\n"
"5592\n"
"5601\n"
"5614\n"
"5615\n"
"5614\n"
"5615\n"
"5616\n"
"5626\n"
"5627\n"
"5629\n"
"5647\n"
"5649\n"
"5650\n"
"5645\n"
"5646\n"
"5647\n"
"5672\n"
"5690\n"
"5692\n"
"5697\n"
"5701\n"
"5697\n"
"5702\n"
"5705\n"
"5718\n"
"5720\n"
"5725\n"
"5747\n"
"5749\n"
"5751\n"
"5756\n"
"5762\n"
"5764\n"
"5771\n"
"5772\n"
"5771\n"
"5772\n"
"5809\n"
"5822\n"
"5823\n"
"5840\n"
"5841\n"
"5839\n"
"5838\n"
"5839\n"
"5840\n"
"5838\n"
"5852\n"
"5853\n"
"5859\n"
"5865\n"
"5879\n"
"5885\n"
"5899\n"
"5907\n"
"5910\n"
"5936\n"
"5943\n"
"5957\n"
"5953\n"
"5958\n"
"5968\n"
"5979\n"
"5971\n"
"5966\n"
"5967\n"
"5971\n"
"5991\n"
"5993\n"
"5994\n"
"5993\n"
"5996\n"
"5993\n"
"6004\n"
"6010\n"
"6017\n"
"6018\n"
"6017\n"
"6038\n"
"6036\n"
"6035\n"
"6036\n"
"6039\n"
"6042\n"
"6037\n"
"6059\n"
"6062\n"
"6067\n"
"6068\n"
"6084\n"
"6077\n"
"6080\n"
"6081\n"
"6079\n"
"6093\n"
"6095\n"
"6098\n"
"6111\n"
"6107\n"
"6114\n"
"6105\n"
"6104\n"
"6111\n"
"6112\n"
"6120\n"
"6126\n"
"6140\n"
"6143\n"
"6142\n"
"6148\n"
"6152\n"
"6159\n"
"6150\n"
"6152\n"
"6168\n"
"6169\n"
"6167\n"
"6161\n"
"6160\n"
"6159\n"
"6160\n"
"6168\n"
"6169\n"
"6188\n"
"6200\n"
"6220\n"
"6221\n"
"6219\n"
"6221\n"
"6220\n"
"6232\n"
"6233\n"
"6234\n"
"6242\n"
"6247\n"
"6246\n"
"6247\n"
"6253\n"
"6258\n"
"6256\n"
"6249\n"
"6228\n"
"6225\n"
"6223\n"
"6227\n"
"6228\n"
"6259\n"
"6265\n"
"6268\n"
"6270\n"
"6271\n"
"6275\n"
"6270\n"
"6263\n"
"6265\n"
"6279\n"
"6323\n"
"6365\n"
"6374\n"
"6397\n"
"6415\n"
"6416\n"
"6419\n"
"6403\n"
"6405\n"
"6410\n"
"6417\n"
"6424\n"
"6425\n"
"6422\n"
"6432\n"
"6442\n"
"6451\n"
"6459\n"
"6458\n"
"6463\n"
"6485\n"
"6486\n"
"6509\n"
"6508\n"
"6532\n"
"6535\n"
"6551\n"
"6562\n"
"6563\n"
"6572\n"
"6571\n"
"6590\n"
"6628\n"
"6629\n"
"6627\n"
"6625\n"
"6620\n"
"6619\n"
"6625\n"
"6616\n"
"6615\n"
"6646\n"
"6648\n"
"6649\n"
"6651\n"
"6653\n"
"6645\n"
"6651\n"
"6652\n"
"6665\n"
"6660\n"
"6664\n"
"6665\n"
"6684\n"
"6685\n"
"6694\n"
"6695\n"
"6696\n"
"6693\n"
"6694\n"
"6703\n"
"6702\n"
"6696\n"
"6693\n"
"6694\n"
"6691\n"
"6725\n"
"6728\n"
"6715\n"
"6722\n"
"6728\n"
"6729\n"
"6730\n"
"6742\n"
"6753\n"
"6754\n"
"6752\n"
"6753\n"
"6761\n"
"6771\n"
"6773\n"
"6778\n"
"6779\n"
"6795\n"
"6819\n"
"6797\n"
"6799\n"
"6798\n"
"6807\n"
"6809\n"
"6837\n"
"6861\n"
"6864\n"
"6865\n"
"6868\n"
"6869\n"
"6867\n"
"6861\n"
"6871\n"
"6874\n"
"6872\n"
"6873\n"
"6875\n"
"6867\n"
"6877\n"
"6876\n"
"6898\n"
"6900\n"
"6902\n"
"6904\n"
"6905\n"
"6915\n"
"6908\n"
"6927\n"
"6928\n"
"6935\n"
"6942\n"
"6943\n"
"6945\n"
"6948\n"
"6943\n"
"6947\n"
"6990\n"
"6993\n"
"7013\n"
"7014\n"
"6997\n"
"6976\n"
"6972\n"
"6975\n"
"6976\n"
"6982\n"
"6991\n"
"7006\n"
"7009\n"
"7015\n"
"7019\n"
"7018\n"
"7008\n"
"7011\n"
"7018\n"
"7023\n"
"7027\n"
"7044\n"
"7054\n"
"7060\n"
"7058\n"
"7057\n"
"7061\n"
"7038\n"
"7036\n"
"7040\n"
"7041\n"
"7039\n"
"7042\n"
"7039\n"
"7037\n"
"7049\n"
"7056\n"
"7057\n"
"7072\n"
"7095\n"
"7101\n"
"7102\n"
"7104\n"
"7103\n"
"7106\n"
"7107\n"
"7108\n"
"7112\n"
"7117\n"
"7119\n"
"7117\n"
"7132\n"
"7130\n"
"7137\n"
"7143\n"
"7135\n"
"7138\n"
"7152\n"
"7156\n"
"7180\n"
"7181\n"
"7182\n"
"7179\n"
"7180\n"
"7174\n"
"7172\n"
"7162\n"
"7177\n"
"7180\n"
"7187\n"
"7153\n"
"7159\n"
"7145\n"
"7139\n"
"7140\n"
"7137\n"
"7156\n"
"7160\n"
"7161\n"
"7162\n"
"7163\n"
"7170\n"
"7163\n"
"7171\n"
"7167\n"
"7166\n"
"7167\n"
"7169\n"
"7170\n"
"7178\n"
"7179\n"
"7166\n"
"7177\n"
"7176\n"
"7203\n"
"7194\n"
"7187\n"
"7191\n"
"7202\n"
"7198\n"
"7199\n"
"7205\n"
"7206\n"
"7207\n"
"7208\n"
"7214\n"
"7215\n"
"7214\n"
"7215\n"
"7217\n"
"7208\n"
"7205\n"
"7214\n"
"7215\n"
"7216\n"
"7212\n"
"7214\n"
"7222\n"
"7226\n"
"7231\n"
"7229\n"
"7239\n"
"7238\n"
"7239\n"
"7250\n"
"7252\n"
"7255\n"
"7277\n"
"7279\n"
"7284\n"
"7290\n"
"7293\n"
"7294\n"
"7316\n"
"7325\n"
"7326\n"
"7327\n"
"7328\n"
"7326\n"
"7325\n"
"7329\n"
"7335\n"
"7340\n"
"7344\n"
"7337\n"
"7338\n"
"7348\n"
"7366\n"
"7376\n"
"7377\n"
"7382\n"
"7387\n"
"7401\n"
"7392\n"
"7396\n"
"7400\n"
"7406\n"
"7405\n"
"7410\n"
"7425\n"
"7426\n"
"7432\n"
"7449\n"
"7450\n"
"7444\n"
"7450\n"
"7455\n"
"7456\n"
"7471\n"
"7472\n"
"7494\n"
"7514\n"
"7515\n"
"7512\n"
"7515\n"
"7517\n"
"7514\n"
"7538\n"
"7539\n"
"7540\n"
"7556\n"
"7557\n"
"7553\n"
"7549\n"
"7546\n"
"7566\n"
"7567\n"
"7564\n"
"7565\n"
"7559\n"
"7560\n"
"7563\n"
"7571\n"
"7570\n"
"7572\n"
"7580\n"
"7587\n"
"7595\n"
"7597\n"
"7614\n"
"7622\n"
"7621\n"
"7627\n"
"7656\n"
"7652\n"
"7659\n"
"7658\n"
"7657\n"
"7660\n"
"7665\n"
"7664\n"
"7666\n"
"7669\n"
"7678\n"
"7680\n"
"7682\n"
"7683\n"
"7669\n"
"7692\n"
"7695\n"
"7699\n"
"7705\n"
"7717\n"
"7720\n"
"7730\n"
"7733\n"
"7748\n"
"7759\n"
"7747\n"
"7748\n"
"7759\n"
"7778\n"
"7777\n"
"7778\n"
"7780\n"
"7781\n"
"7780\n"
"7788\n"
"7787\n"
"7788\n"
"7814\n"
"7810\n"
"7787\n"
"7788\n"
"7802\n"
"7803\n"
"7813\n"
"7815\n"
"7818\n"
"7823\n"
"7830\n"
"7852\n"
"7868\n"
"7874\n"
"7879\n"
"7873\n"
"7854\n"
"7871\n"
"7877\n"
"7876\n"
"7883\n"
"7885\n"
"7887\n"
"7886\n"
"7889\n"
"7893\n"
"7900\n"
"7909\n"
"7910\n"
"7906\n"
"7910\n"
"7913\n"
"7918\n"
"7919\n"
"7941\n"
"7947\n"
"7948\n"
"7949\n"
"7951\n"
"7952\n"
"7977\n"
"7976\n"
"7979\n"
"8010\n"
"8011\n"
"8014\n"
"8015\n"
"8031\n"
"8054\n"
"8056\n"
"8059\n"
"8085\n"
"8087\n"
"8107\n"
"8109\n"
"8115\n"
"8116\n"
"8117\n"
"8115\n"
"8116\n"
"8119\n"
"8127\n"
"8145\n"
"8147\n")
matches = re.finditer(regex, test_str, re.MULTILINE)
for matchNum, match in enumerate(matches, start=1):
print ("Match {matchNum} was found at {start}-{end}: {match}".format(matchNum = matchNum, start = match.start(), end = match.end(), match = match.group()))
for groupNum in range(0, len(match.groups())):
groupNum = groupNum + 1
print ("Group {groupNum} found at {start}-{end}: {group}".format(groupNum = groupNum, start = match.start(groupNum), end = match.end(groupNum), group = match.group(groupNum)))
# Note: for Python 2.7 compatibility, use ur"" to prefix the regex and u"" to prefix the test string and substitution.
Please keep in mind that these code samples are automatically generated and are not guaranteed to work. If you find any syntax errors, feel free to submit a bug report. For a full regex reference for Python, please visit: https://docs.python.org/3/library/re.html