Problem:


Score : 400 points

Problem Statement

Given is a positive integer N. Consider repeatedly applying the operation below on N:

First, choose a positive integer z satisfying all of the conditions below:

z can be represented as z=p^e, where p is a prime number and e is a positive integer;

z divides N;

z is different from all integers chosen in previous operations.

Then, replace N with N/z.

Find the maximum number of times the operation can be applied.

Constraints

All values in input are integers.

1 \leq N \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N

Output

Print the maximum number of times the operation can be applied.

Sample Input 1

24

Sample Output 1

3

We can apply the operation three times by, for example, making the following choices:

Choose z=2 (=2^1). (Now we have N=12.)

Choose z=3 (=3^1). (Now we have N=4.)

Choose z=4 (=2^2). (Now we have N=1.)

Sample Input 2

1

Sample Output 2

0

We cannot apply the operation at all.

Sample Input 3

64

Sample Output 3

3

We can apply the operation three times by, for example, making the following choices:

Choose z=2 (=2^1). (Now we have N=32.)

Choose z=4 (=2^2). (Now we have N=8.)

Choose z=8 (=2^3). (Now we have N=1.)

Sample Input 4

1000000007

Sample Output 4

1

We can apply the operation once by, for example, making the following choice:

z=1000000007 (=1000000007^1). (Now we have N=1.)

Sample Input 5

997764507000

Sample Output 5

7



Sample input:
24


Sample output:
3

Submission status: Wrong Answer

Solution code:
sosu = [2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293, 307, 311, 313, 317, 331, 337, 343, 347, 349, 353, 359, 361, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 529, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 625, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 841, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 961, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1331, 1361, 1367, 1369, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1681, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1849, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2197, 2203, 2207, 2209, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2401, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2809, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3481, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3721, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4489, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4913, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5041, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5329, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6241, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6859, 6863, 6869, 6871, 6883, 6889, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7921, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9409, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10201, 10609, 11449, 11881, 12167, 12769, 14641, 16129, 17161, 18769, 19321, 22201, 22801, 24389, 24649, 26569, 27889, 28561, 29791, 29929, 32041, 32761, 36481, 37249, 38809, 39601, 44521, 49729, 50653, 51529, 52441, 54289, 57121, 58081, 63001, 66049, 68921, 69169, 72361, 73441, 76729, 78961, 79507, 80089, 83521, 85849, 94249, 96721, 97969, 100489, 103823, 109561, 113569, 120409, 121801, 124609, 128881, 130321, 134689, 139129, 143641, 146689, 148877, 151321, 157609, 160801, 167281, 175561, 177241, 185761, 187489, 192721, 196249, 201601, 205379, 208849, 212521, 214369, 218089, 226981, 229441, 237169, 241081, 249001, 253009, 259081, 271441, 273529, 279841, 292681, 299209, 300763, 310249, 316969, 323761, 326041, 332929, 344569, 351649, 357911, 358801, 361201, 368449, 375769, 380689, 383161, 389017, 398161, 410881, 413449, 418609, 426409, 434281, 436921, 452929, 458329, 466489, 477481, 491401, 493039, 502681, 516961, 528529, 537289, 546121, 552049, 564001, 571787, 573049, 579121, 591361, 597529, 619369, 635209, 654481, 657721, 674041, 677329, 683929, 687241, 703921, 704969, 707281, 727609, 734449, 737881, 744769, 769129, 776161, 779689, 786769, 822649, 829921, 844561, 863041, 877969, 885481, 896809, 908209, 912673, 923521, 935089, 942841, 954529, 966289, 982081, 994009, 1018081, 1026169, 1030301, 1038361, 1042441, 1062961, 1067089, 1079521, 1092727, 1100401, 1104601, 1125721, 1129969, 1142761, 1181569, 1190281, 1194649, 1203409, 1216609, 1225043, 1229881, 1247689, 1261129, 1274641, 1295029, 1324801, 1329409, 1352569, 1371241, 1394761, 1408969, 1423249, 1442401, 1442897, 1471369, 1481089, 1495729, 1510441, 1515361, 1530169, 1560001, 1585081, 1630729, 1635841, 1646089, 1661521, 1666681, 1682209, 1692601, 1697809, 1708249, 1739761, 1745041, 1760929, 1852321, 1868689, 1874161, 1885129, 1907161, 1957201, 1985281, 2024929, 2036329, 2042041, 2048383, 2053489, 2070721, 2093809, 2105401, 2111209, 2128681, 2163841, 2193361, 2199289, 2211169, 2217121, 2229049, 2247001, 2248091, 2283121, 2319529, 2343961, 2380849, 2399401, 2411809, 2430481, 2455489, 2468041, 2493241, 2505889, 2550409, 2563201, 2571353, 2582449, 2588881, 2601769, 2621161, 2627641, 2647129, 2679769, 2685619, 2745649, 2765569, 2778889, 2785561, 2825761, 2866249, 2879809, 2886601, 2920681, 2961841, 2968729, 3003289, 3031081, 3052009, 3073009, 3094081, 3157729, 3179089, 3193369, 3200521, 3243601, 3279721, 3307949, 3323329, 3352561, 3411409, 3418801, 3442951, 3463321, 3485689, 3500641, 3508129, 3523129, 3530641, 3568321, 3613801, 3636649, 3659569, 3728761, 3736489, 3798601, 3806401, 3869893, 3892729, 3916441, 3948169, 3972049, 3988009, 3996001, 4012009, 4044121, 4068289, 4108729, 4116841, 4157521, 4214809, 4255969, 4280761, 4330561, 4330747, 4338889, 4355569, 4363921, 4405801, 4456321, 4464769, 4532641, 4541161, 4566769, 4583881, 4592449, 4635409, 4657463, 4669921, 4748041, 4853209, 4870849, 4879681, 4897369, 4932841, 5004169, 5013121, 5031049, 5067001, 5139289, 5148361, 5166529, 5177717, 5202961, 5230369, 5257849, 5276209, 5331481, 5340721, 5442889, 5470921, 5480281, 5508409, 5527201, 5555449, 5621641, 5650129, 5669161, 5678689, 5707321, 5726449, 5735339, 5755201, 5812921, 5841889, 5870929, 5929741, 5938969, 5958481, 5987809, 6046681, 6086089, 6115729, 6135529, 6265009, 6355441, 6405961, 6446521, 6466849, 6497401, 6507601, 6538249, 6651241, 6713281, 6723649, 6806881, 6848689, 6869641, 6932689, 6967871, 7006609, 7059649, 7070281, 7091569, 7134241, 7166329, 7189057, 7198489, 7219969, 7230721, 7252249, 7284601, 7327849, 7349521, 7360369, 7392961, 7447441, 7458361, 7513081, 7557001, 7579009, 7645373, 7656289, 7711729, 7778521, 7789681, 7823209, 7845601, 7856809, 7880599, 7890481, 7946761, 8025889, 8048569, 8082649, 8128201, 8162449, 8185321, 8288641, 8334769, 8392609, 8427409, 8462281, 8508889, 8567329, 8637721, 8720209, 8743849, 8779369, 8814961, 8826841, 8994001, 9006001, 9066121, 9114361, 9138529, 9223369, 9247681, 9296401, 9369721, 9393931, 9406489, 9480241, 9504889, 9541921, 9665881, 9728161, 9740641, 9840769, 10004569, 10029889, 10042561, 10118761, 10156969, 10182481, 10259209, 10297681, 10349089, 10374841, 10426441, 10569001, 10582009, 10608049, 10621081, 10699441, 10883401, 10896601, 10936249, 10975969, 11015761, 11042329, 11082241, 11089567, 11095561, 11175649, 11202409, 11282881, 11296321, 11363641, 11377129, 11485321, 11498881, 11607649, 11648569, 11697083, 11785489, 11895601, 11950849, 11978521, 11992369, 12008989, 12020089, 12033961, 12117361, 12187081, 12243001, 12327121, 12369289, 12439729, 12453841, 12482089, 12524521, 12538681, 12581209, 12649337, 12652249, 12666481, 12752041, 12823561, 12837889, 12909649, 13010449, 13053769, 13082689, 13126129, 13184161, 13227769, 13271449, 13388281, 13476241, 13490929, 13520329, 13623481, 13651919, 13667809, 13697401, 13756681, 13830961, 13845841, 13890529, 13935289, 13980121, 13997521, 14145121, 14190289, 14205361, 14280841, 14386849, 14417209, 14462809, 14600041, 14615329, 14691889, 14799409, 14830201, 14845609, 14922769, 15031129, 15062161, 15124321, 15264649, 15295921, 15342889, 15358561, 15389929, 15437041, 15452761, 15547249, 15578809, 15737089, 15813251, 15912121, 16008001, 16024009, 16056049, 16104169, 16152361, 16168441, 16216729, 16394401, 16410601, 16459249, 16589329, 16638241, 16736281, 16752649, 16801801, 16900321, 16974593, 17032129, 17048641, 17081689, 17131321, 17247409, 17280649, 17297281, 17447329, 17648401, 17732521, 17783089, 17799961, 17884441, 17901361, 17986081, 18003049, 18088009, 18139081, 18156121, 18191447, 18241441, 18258529, 18344089, 18395521, 18464209, 18722929, 18809569, 18826921, 18913801, 18983449, 19035769, 19123129, 19280881, 19333609, 19439281, 19465109, 19545241, 19562929, 19722481, 19775809, 19811401, 19864849, 19902511, 19918369, 20079361, 20097289, 20151121, 20187049, 20313049, 20367169, 20403289, 20421361, 20457529, 20675209, 20693401, 20802721, 20857489, 21003889, 21077281, 21132409, 21187609, 21253933, 21353641, 21501769, 21520321, 21557449, 21613201, 21631801, 21687649, 21743569, 21836929, 21893041, 22005481, 22118209, 22188041, 22287841, 22306729, 22363441, 22401289, 22572001, 22648081, 22665187, 22877089, 22915369, 22934521, 22972849, 23030401, 23049601, 23164969, 23203489, 23338561, 23629321, 23726641, 23785129, 23902321, 24039409, 24098281, 24196561, 24314761, 24334489, 24373969, 24433249, 24512401, 24571849, 24671089, 24690961, 24730729, 24870169, 24930049, 24990001, 25030009, 25090081, 25110121, 25153757, 25210441, 25230529, 25391521, 25411681, 25512601, 25593481, 25775929, 25816561, 25877569, 25999801, 26020201, 26081449, 26142769, 26204161, 26491609, 26553409, 26697889, 26739241, 26822041, 26925721, 27008809, 27133681, 27321529, 27363361, 27384289, 27426169, 27678121, 27804529, 27867841, 27888961, 28058209, 28121809, 28185481, 28334329, 28398241, 28440889, 28590409, 28633201, 28934443, 28955161, 29019769, 29084449, 29149201, 29235649, 29300569, 29343889, 29365561, 29495761, 29560969, 29604481, 29626249, 29691601, 29931841, 29997529, 30019441, 30063289, 30080231, 30261001, 30283009, 30327049, 30459361, 30481441, 30547729, 30591961, 30664297, 30880249, 30946969, 31013761, 31058329, 31147561, 31259281, 31618129, 31798321, 31820881, 31855013, 31888609, 31933801, 31956409, 32001649, 32024281, 32137561, 32296489, 32364721, 32410249, 32501401, 32615521, 32684089, 32913169, 32959081, 32982049, 33051001, 33396841, 33443089, 33535681, 33651601, 33721249, 33790969, 33884041, 33953929, 34093921, 34140649, 34210801, 34234201, 34304449, 34351321, 34421689, 34445161, 34562641, 34586161, 34774609, 34845409, 35081929, 35129329, 35271721, 35438209, 35772361, 35844169, 36084049, 36132121, 36264691, 36348841, 36445369, 36517849, 36566209, 36638809, 36808489, 36881329, 36954241, 37075921, 37100281, 37222201, 37368769, 37466641, 37589161, 37613689, 37736449, 37834801, 37982569, 38105929, 38272753, 38402809, 38427601, 38477209, 38576521, 38651089, 38700841, 38800441, 38950081, 39025009, 39150049, 39225169, 39300361, 39325441, 39400729, 39526369, 39677401, 39702601, 39828721, 39904489, 39980329, 40056241, 40157569, 40233649, 40360609, 40436881, 40462321, 40538689, 40615129, 40691641, 40819321, 40921609, 41229241, 41306329, 41589601, 41615401, 41781923, 41847961, 41899729, 42003361, 42133081, 42508549, 42523441, 42627841, 42863209, 42915601, 42941809, 43072969, 43151761, 43178041, 43256929, 43309561, 43546801, 43652449, 43811161, 43986977, 44049769, 44262409, 44342281, 44368921, 44528929, 44609041, 44742721, 44769481, 44903401, 44930209, 45010681, 45144961, 45333289, 45387169, 45711121, 45738169, 45954841, 45981961, 46117681, 46144849, 46268279, 46280809, 46553329, 46607929, 46635241, 46689889, 46799281, 47018449, 47100769, 47183161, 47210641, 47375689, 47458321, 47596201, 47706649, 47761921, 47844889, 48260809, 48288601, 48427681, 48455521, 48539089, 48594841, 48678529, 48762289, 48874081, 48958009, 49014001, 49182169, 49266361, 49378729, 49430863, 49547521, 49603849, 49801249, 49970761, 50112241, 50452609, 50537881, 50708641, 50794129, 50822641, 51136801, 51251281, 51509329, 51652969, 51739249, 51895117, 51940849, 51998521, 52027369, 52113961, 52258441, 52374169, 52461049, 52519009, 52606009, 53042089, 53246209, 53392249, 53421481, 53597041, 53743561, 53772889, 54007801, 54037201, 54302161, 54439939, 54656449, 54922921, 55011889, 55249489, 55517401, 55606849, 55636681, 55905529, 55965361, 56055169, 56085121, 56181887, 56235001, 56355049, 56505289, 56595529, 56685841, 56806369, 56866681, 56957209, 56987401, 57138481, 57168721, 57350329, 57410929, 57501889, 57592921, 57623281, 57805609, 57866449, 58079641, 58354321, 58415449, 58507201, 58813561, 58863869, 58874929, 58997761, 59089969, 59151481, 59274601, 59336209, 59552089, 59644729, 59706529, 59923081, 60109009, 60171049, 60202081, 60668521, 60730849, 61105489, 61199329, 61293241, 61481281, 61669609, 61889689, 61984129, 62047129, 62078641, 62141689, 62425801, 62520649, 62570773, 62710561, 62742241, 62837329, 62932489, 62995969, 63186601, 63218401, 63409369, 63888049, 64144081, 64176121, 64272289, 64481201, 64625521, 64850809, 64947481, 65108761, 65302561, 65399569, 65431921, 65496649, 65626201, 65788321, 65885689, 65983129, 66373609, 66601921, 66699889, 66765241, 66896041, 67092481, 67387681, 67551961, 67584841, 67749361, 67782289, 67848169, 67947049, 68277169, 68376361, 68417929, 68442529, 68674369, 68740681, 68773849, 68840209, 69072721, 69172489, 69372241, 69772609, 69939769, 70040161, 70174129, 70341769, 70375321, 70879561, 70946929, 71048041, 71081761, 71284249, 71351809, 71588521, 71690089, 72267001, 72471169, 72607441, 72709729, 72880369, 72914521, 72982849, 73324969, 73496329, 73560059, 73633561, 73908409, 73942801, 74114881, 74356129, 74425129, 74459641, 74618461, 74666881, 74770609, 75047569, 75151561, 75290329, 75359761, 75498721, 75568249, 75672601, 75811849, 75916369, 76020961, 76230361, 76335169, 76405081, 76510009, 76615009, 76755121, 77070841, 77141089, 77492809, 77563249, 77774761, 77810041, 77986561, 78092569, 78127921, 78304801, 78517321, 78552769, 78623689, 78978769, 79085449, 79619929, 79727041, 79798489, 79941481, 80062991, 80120401, 80335369, 80442961, 80478841, 80982001, 81018001, 81126049, 81182737, 81198121, 81234169, 81522841, 81739681, 81775849, 81884401, 82065481, 82210489, 82646281, 82864609, 82973881, 83302129, 83411689, 83484769, 83740801, 83850649, 83923921, 84143929, 84290761, 84400969, 84604519, 84621601, 84695209, 84805681, 85026841, 85137529, 85359121, 85396081, 85692049, 86062729, 86136961, 86174089, 86359849, 86694721, 86843761, 86918329, 86938307, 87179569, 87254281, 87291649, 87403801, 87815641, 87928129, 88190881, 88303609, 88416409, 88529281, 88604569, 88717561, 88755241, 88943761, 88981489, 89056969, 89094721, 89510521, 89548369, 89624089, 89737729, 89851441, 90079081, 90193009, 90459121, 90518849, 90649441, 90878089, 90992521, 91145209, 91221601, 91910569, 92179201, 92409769, 92525161, 92602129, 92717641, 92756161, 92987449, 93103201, 93334921, 93644329, 93683041, 93876721, 94031809, 94458961, 94497841, 94731289, 94848121, 94926049, 95043001, 95394289, 95433361, 95443993, 95667961, 95785369, 95863681, 96098809, 96255721, 96373489, 96609241, 96687889, 96805921, 97042201, 97160449, 97199881, 97436641, 97673689, 97752769, 97972181, 98029801, 98148649, 98465929, 98585041, 98624761, 98823481, 98982601, 99252847, 99341089, 99460729, 100140049, 101847563, 104060401, 109902239, 112550881, 115501303, 118370771, 124251499, 127263527, 131079601, 131872229, 141158161, 141420761, 143055667, 158340421, 163047361, 163667323, 172808693, 178453547, 184220009, 186169411, 192100033, 202262003, 208527857, 214921799, 217081801, 223648543, 230346397, 234885113, 237176659, 251239591, 260144641, 263374721, 265847707, 270840023, 278445077, 286191179, 288804781, 294499921, 304821217, 310288733, 318611987, 329939371, 344472101, 352275361, 356400829, 371694959, 373301041, 384240583, 393832837, 403583419, 410172407, 423564751, 433798093, 440711081, 454756609, 461889917, 487443403, 492884401, 506261573, 519885601, 529475129, 533411731, 553387661, 557441767, 565609283, 569722789, 590589719, 607573201, 620650477, 629422793, 633839779, 642735647, 674526133, 683797841, 688465387, 697864103, 705911761, 746142643, 756058031, 776151559, 777796321, 801765089, 822656953, 833237621, 849278123, 865523177, 895745041, 904231063, 915498611, 932574833, 949862087, 973242271, 991026973, 1026625681, 1027243729, 1039509197, 1058089859, 1064332261, 1073283121, 1095912791, 1102302937, 1121622319, 1154320649, 1160935651, 1194389981, 1201157047, 1221611509, 1284365503, 1298596571, 1305751357, 1320139673, 1330863361, 1341919727, 1363938029, 1387488001, 1393668613, 1416247867, 1439069689, 1506138481, 1524845951, 1532808577, 1568239201, 1573037747, 1605723211, 1647212741, 1672446203, 1697936057, 1732323601, 1784770597, 1802485313, 1829276567, 1856331989, 1865409391, 1892819053, 1948441249, 1982119441, 1995616979, 2082440933, 2092240639, 2111932187, 2141700569, 2151685171, 2181825073, 2202073901, 2212245127, 2232681443, 2294744759, 2305199161, 2336752783, 2472973441, 2521008881, 2554497863, 2588282117, 2633789341, 2655237841, 2738124199, 2750058481, 2797260929, 2881473967, 2905841483, 2918076589, 2942649737, 2947295521, 2979767519, 3029741623, 3054936851, 3067586677, 3105745579, 3183010111, 3248367641, 3261545587, 3262808641, 3288008303, 3301293169, 3327970157, 3368254499, 3373402561, 3449795831, 3532642667, 3588604291, 3673650007, 3716672149, 3745539377, 3789119879, 3847751263, 3877292411, 3936827539, 3966822287, 3969126001, 4073003173, 4103684801, 4149995543, 4165509529, 4196653397, 4243659659, 4259406061, 4306878883, 4362470401, 4386781853, 4549540393, 4599141247, 4632407963, 4649101309, 4784350561, 4852559557, 4887035873, 4904335099, 4991443829, 5097328361, 5115120067, 5204699837, 5236114321, 5277112021, 5331859723, 5386984777, 5393580481, 5442488479, 5611284433, 5668315687, 5706550403, 5725732069, 5841725401, 5887339441, 5939574731, 6058428767, 6138539191, 6234839521, 6300872423, 6414247921, 6445240381, 6507781363, 6549699311, 6570725617, 6612913133, 6634074439, 6740558369, 6869835701, 6935089643, 7000755497, 7200237491, 7222633237, 7370050801, 7403473349, 7426288351, 7680354317, 7750636739, 7845011803, 7916293657, 7964053973, 7988005999, 8036054027, 8132727331, 8205738913, 8328393683, 8353070389, 8477185319, 8653002877, 8780064047, 8856894509, 8882874001, 9011897441, 9037905787, 9090072503, 9116230969, 9247776299, 9354951841, 9407293631, 9434056897, 9597924961, 9649992689, 9677214091, 9759185353, 9814089221, 9841618207, 9980035577, 10091699281, 10098039121, 10345981339, 10691619427, 10749963743, 10837877597, 10955839861, 11194326053, 11224377919, 11284642907, 11405819251, 11650768163, 11681631109, 11743520417, 11867954041, 11961853903, 12003612721, 12056247757, 12119452073, 12310389629, 12342406231, 12698260037, 12796484219, 12829337821, 12897917761, 12928235923, 12994449551, 13094193293, 13328910811, 13430356633, 13498272341, 13532315887, 13634789869, 13703392457, 13806727199, 14014952531, 14119845713, 14225260967, 14473267453, 14498327281, 14544652121, 14652168623, 14835483601, 14868788579, 15014381563, 15124197817, 15197705333, 15527402881, 15681317527, 16022066761, 16213487291, 16367716819, 16445197007, 16561875149, 16600890151, 16610312161, 16718302693, 17153550539, 17394111071, 17434421857, 17759152529, 17923019113, 18005329061, 18141126721, 18253770137, 18546494023, 18757487393, 18799877179, 18884848247, 19055557711, 19184262733, 19313545987, 19356878641, 19400056703, 19443408769, 19530306557, 19661138099, 19836487243, 19924551431, 19968681097, 20101460959, 20324066489, 20368783891, 20593355021, 20632736881, 20774195749, 20865011777, 21184951663, 21415471433, 21517662721, 21694295069, 21740999671, 21881515573, 21975528401, 22022635627, 22401919259, 22737343537, 22833790253, 22898045041, 22978971107, 23173501051, 23320116793, 23418203381, 23862997439, 24062478103, 24313388273, 24464768327, 24616775429, 24820429213, 24840596881, 25076571983, 25386262019, 25750777177, 25855561493, 25856961601, 26013270347, 26171619209, 26224544611, 26973008999, 27027009001, 27298090331, 27516255859, 27625773167, 27982932961, 28011371653, 28122197921, 28344726649, 28680715981, 28849701763, 29189662039, 29303572787, 29474993969, 30051224029, 30342134159, 30400540561, 30821664721, 30870492353, 31414372081, 31644451747, 31764658463, 31824875809, 32187778741, 32370260203, 32492296871, 32860246427, 33045258329, 33293019313, 33417362861, 33666977989, 34359822251, 34423275277, 34507149121, 34550415593, 34614102979, 34997871511, 35152125121, 35904339899, 35969679901, 36166175443, 36363385297, 36561310759, 36693659267, 36892780289, 36959313691, 37141383841, 37360194607, 37494462923, 37899197279, 37966934881, 38306833811, 38375056117, 38513670001, 38923752869, 38992705471, 39547260143, 39756565997, 40459583737, 40642963201, 41027927849, 41314084993, 41457661181, 41529573847, 41673648563, 41745810709, 42545099771, 42838260499, 43280521831, 43502789413, 43617904801, 43874924183, 43949604889, 44099220437, 44324279819, 44399469421, 44625548323, 45004049693, 45080005879, 45165175441, 45537538411, 45921171941, 45954068161, 45998156287, 46384368857, 46928689543, 47163267397, 47320086113, 47555965367, 47562811921, 47871688591, 48109395853, 48347888707, 48987720179, 49471280711, 49552182217, 49714249733, 50284268371, 50529889873, 50694081101, 51023529829, 51437343959, 51770001583, 52020433837, 52271672419, 52643172481, 53199800081, 53454818663, 53540005609, 53967298139, 54569318257, 54742142573, 55002062627, 55786756661, 55874402767, 56249134561, 56314010537, 56933326423, 57111104051, 57200131477, 57646656647, 58120048561, 58275687133, 58456246841, 58818484369, 59638983643, 59822347031, 60098096213, 60190200559, 60374691467, 60652134089, 60744803491, 61302802807, 61489559123, 62001498001, 62429032063, 63473450669, 64013554081, 64048012001, 64144108027, 64336588343, 64626030197, 64916338859, 65013301261, 65304767683, 66380929649, 66479344651, 66775173193, 67122964561, 67568337017, 67867385039, 68468125571, 68568592357, 68870582299, 69477219631, 70291596383, 70393838689, 70598620637, 70906537619, 71628489577, 71835657893, 71939391679, 72877493233, 73680216481, 74140932601, 74671645931, 74818113841, 74991286313, 75098035459, 75633300989, 75740658391, 76278969521, 76386936907, 76928302277, 77254345979, 77363231581, 77909194511, 78018694417, 78567733187, 78898389569, 79340706073, 81014113783, 81577100753, 81690010219, 82256120549, 82710887293, 83053060147, 83625443117, 84662348471, 85009878773, 85662167761, 85707789929, 86409510461, 86526834967, 87587538121, 87943022623, 88180545851, 88537631993, 88895680847, 89526025681, 89975616641, 90096146587, 90700411157, 91550911843, 91917033697, 92161656413, 92284130359, 92529403667, 94010175323, 94134281149, 94881210481, 95256152263, 96254442001, 96260823287, 96765797071, 97145684173, 97526564227, 98675175061, 99703702853, 99832769119, 100091235707, 100469346961, 100479771449, 100609506451, 100999381393, 101390262247, 102043969217, 102437538839, 103227711371, 104021936927, 104821185121, 105220897361, 105354681067, 105756712489, 106025300837, 106302733681, 107239576751, 107782217479, 109421116687, 109695871403, 109833421069, 110108865257, 110522894399, 110661134401, 110841719041, 111492995797, 111771206513, 112748588191, 114862129381, 115572468311, 116000074133, 116858447369, 117865222327, 118298461429, 118727795761, 119022883559, 119896086491, 120042034237, 120334284953, 120773549807, 121360897351, 121802655493, 122541299063, 122689385209, 122985915317, 123657019201, 124027532803, 124475734657, 124925014999, 125225135027, 125676215729, 125826816331, 126581624261, 126732947167, 127947874319, 128738157601, 128864147651, 129477420379, 130466162401, 130864391533, 131173946441, 131639193503, 132572985299, 132729045301, 133197960043, 133667977897, 134139100159, 135754665601, 136352311523, 136829716577, 137947992463, 138268615211, 138911350339, 139717566269, 140364780373, 141202341361, 141339344329, 142809632083, 143137741391, 143301984337, 143630847053, 144924114721, 145614594581, 146613281417, 146812351921, 147114332639, 147281603041, 148624333073, 149129953127, 149636718629, 150823633267, 151675261037, 152872916923, 153216258551, 155807721341, 156329495603, 156852433457, 157376536199, 158077154143, 158532181921, 158603979997, 158955846713, 159131975059, 160191477991, 160722988453, 161077981121, 161255673307, 161789533849, 163757102111, 164296466333, 164476517239, 164837013587, 166465766501, 166647398527, 167011058843, 168105213359, 168288035761, 168823196161, 168837298183, 169204136291, 170940075601, 171601543693, 172157988547, 172715635009, 173088067517, 173834537941, 174770640071, 175233494881, 177788739367, 179310732119, 179501589721, 180074975023, 180457909451, 180649580077, 181033328393, 181225406179, 181824635281, 182187833309, 183540946987, 184122897769, 184511547557, 185290487101, 186267240431, 186854936813, 188599986961, 188822850553, 189218084021, 189415907407, 190010204749, 190899960241, 193000344139, 193401383687, 194205128671, 195212937401, 195819292943, 196426902797, 197239002661, 197849544283, 199074404719, 199483812107, 200098975049, 200304310051, 200921157793, 201333092381, 201952049363, 202158649909, 203193766439, 203401212841, 205065869273, 205144679041, 205692449327, 207790265467, 208211532983, 209478751019, 210065472241, 210963658177, 213954491141, 214599039803, 216756882343, 217190179331, 217611987121, 219147162389, 220020692653, 220677361507, 221115865823, 221774710877, 223317102763, 223980311017, 224644831039, 225755282969, 225977811571, 227092648301, 227988105361, 228435284897, 229333309561, 230459146091, 230684754637, 231815006207, 232721860951, 234086572747, 235227899717, 237982207373, 238212698599, 238674127427, 239598771931, 240293820313, 240757931861, 241474942801, 241687946989, 243789231223, 244961856593, 245667233447, 246373963109, 246609840511, 247318375933, 248502281903, 249927948899, 250166088901, 251359058231, 252076657013, 252688187761, 252795620267, 253515949289, 254478514753, 255202035607, 256410948977, 257138126279, 257380823881, 258109832863, 258840217117, 259571977939, 260794641869, 261775532773, 264732956461, 265475776483, 267248675521, 268211336849, 268460951851, 270714459709, 271216945817, 272223782641, 273485828771, 277295358761, 278317173889, 279342903841, 280625429323, 281140102151, 281397674377, 282687895547, 283463918009, 283722907411, 284500822033, 285020220941, 287365339799, 288411730543, 288679469521, 289986074659, 292358316853, 294477807077, 295275249179, 295541382781, 297141543217, 297943784839, 298248146641, 299284060769, 299552597371, 300897690101, 301167190927, 301976658829, 303328992959, 304758098401, 305229034837, 305773357553, 309052889081, 309327236947, 311527867139, 311803677541, 313185171671, 313461959257, 314848343627, 317633363767, 318097128001, 318192331283, 318472060789, 319032011537, 320153881321, 322405504793, 323252577647, 324101132909, 324384314311, 326086867387, 328366190699, 328385156401, 329509824643, 330082636031, 330943097213, 335267840123, 335381132641, 335557488349, 337008232079, 337298881681, 338171833063, 338754636611, 339630096833, 340507064087, 341678700271, 342559188973, 343147021001, 344914551197, 345800587859, 346984328683, 348765000319, 349359908507, 349707832321, 351447414193, 353243309509, 354744554039, 357040905841, 358364881727, 359273796029, 361096232561, 362009757383, 362314607689, 365679263951, 366907920679, 369682454233, 371229888203, 372160418057, 374337698743, 374961334931, 375273412597, 376210684459, 377776269989, 379031861053, 379975377907, 380605258223, 381551383277, 383617958161, 386305534187, 388537587073, 390137163443, 390457604629, 392383937161, 393994045691, 394316595037, 396903329549, 397227464551, 400152624409, 403490473681, 404075127457, 407033767531, 408023180713, 410669451737, 413660154851, 414660272993, 414994003579, 418005640333, 418676865641, 419685050303, 420021471169, 421706272499, 423057352843, 424750257413, 425768164667, 426787696889, 428149603153, 428345379361, 428831641421, 429856056323, 430197890149, 431909777879, 432252699481, 432596913841, 434314041517, 435002609033, 436036824287, 437072677469, 437418326071, 439496045227, 440190077543, 442624944061, 445768658119, 446469276707, 447521580449, 451041199309, 451747330217, 453161802241, 454224591703, 454331269681, 454934040371, 456355153099, 457066817927, 458774574241, 459563470813, 460636242067, 461352349583, 463864570021, 466025146777, 466746827093, 467107946479, 467758877041, 472300192081, 472547110069, 473275506257, 477661607513, 478762350767, 479864783789, 482074724321, 484291439477, 486886183363, 488001047617, 488745235133, 489117612439, 489862934387, 493226253701, 494350771643, 495504774241, 496604932559, 498111506983, 499243435237, 499999005953, 502270291349, 502649506351, 504928805347, 510657175657, 513729944729, 514114905331, 515270940913, 519524563319, 522243564877, 523411749379, 525362592509, 527709995441, 528886314503, 529278808969, 529414856881, 530064380357, 531637854301, 533609071631, 534794137613, 535980956867, 539415333601, 540745792523, 543538277281, 544468370161, 544737993463, 545538784211, 547142719339, 549554511871, 553185473329, 554680863361, 555209567459, 555614977861, 557644990391, 558051585337, 558865368053, 560087524907, 564174247447, 565404129109, 566225042417, 569104495903, 569928986171, 570341529757, 571167214073, 574063384231, 575307591013, 577801395289, 582810602977, 584906288147, 586166107409, 587848678633, 589956416603, 590378567869, 591559418641, 596735024059, 597585982967, 598863937589, 599290326991, 601852914307, 602425897921, 602708730623, 605710476181, 606999983563, 607914936721, 614341775501, 616947061697, 618688004761, 619005459361, 619995859183, 622179710153, 622617094819, 623492479007, 627881709547, 630084028517, 631849586941, 635390592173, 635834145799, 638055010529, 641172900367, 642065587883, 642512242189, 645196518721, 646541456023, 650137090247, 651488882309, 653294184733, 654198085241, 656008386769, 656914788557, 658275956099, 660093769243, 661459323097, 662826758959, 665567281891, 666940371553, 667856813021, 669233048723, 670611173777, 672451615081, 676604913139, 676751377201, 677530184687, 682169197627, 683099533943, 685895617259, 686362371661, 688699320191, 688768866241, 690104032253, 690572693719, 692919184049, 695741981381, 696213191647, 697156250363, 701884320103, 703306897957, 710448626467, 711882749089, 712839902237, 713283282721, 714756781621, 717157709351, 720045912347, 721492917209, 721975682611, 728757026999, 729243027001, 730702323343, 731676268331, 732163565197, 736069731389, 739008455921, 739499002507, 740971944649, 743431192379, 744839767681, 745402503763, 751337340571, 754316535727, 755809082029, 760298531383, 761798955637, 762800334353, 766312069951, 767820392893, 768827040281, 770829564961, 771852260717, 773873476741, 775391702203, 778434107599, 779450008427, 780975516329, 784032500861, 784076601361, 785563980083, 788632918919, 789145184521, 793251297593, 798403936933, 799437135041, 799954068187, 802542076757, 804266382481, 807214547231, 809297008759, 810339581267, 813995635753, 815042238821, 815565876607, 817138135549, 822920371811, 824502065633, 824843587681, 828200563471, 829789013773, 831379493827, 834034807997, 835630707059, 836163125461, 838828609991, 839362385737, 840430616453, 840965071519, 846859039181, 847396215847, 848471250563, 850085506817, 851701809239, 854940557771, 856563006473, 860356699831, 863073327761, 866340822437, 867977657819, 870163310323, 871257511151, 874391437921, 881146625003, 885012508801, 888335109397, 888949151281, 889999523659, 891110287367, 892778165189, 893334586591, 896677970707, 898352786449, 901708671781, 906196171733, 906758153839, 909571549769, 911125611841, 911826451873, 918046641959, 918613512361, 922019635837, 923725850419, 924864495407, 926574216749, 931716020663, 932288503609, 933714431521, 935728326541, 937451406403, 938601300671, 942056624627, 944364878731, 946098541513, 949572229789, 950732012537, 952473456719, 955962722051, 957710545793, 958293626779, 961797083311, 964483090561, 965309068387, 966481627103, 970593059701, 972358665643, 977077413467, 978850872089, 979442501491, 982404224621, 984777897349, 988053892081, 990132634063, 991921850317, 1002101470343, 1036488922561, 1053022816561, 1078193566321, 1086683238481, 1129886087521, 1138678933921, 1165365589441, 1210882360801, 1220143369201, 1267247769841, 1276829940961, 1305902703121, 1396105301761, 1416768858961, 1427186233201, 1448193221281, 1480137458881, 1512607274161, 1556727840721, 1590446354641, 1624709678881, 1755097689601, 1767328289281, 1829442899761, 1880301880081, 1945358247121, 1985193642961, 2025637716001, 2080520644801, 2164926734161, 2193624625921, 2237205241441, 2281432014481, 2296318960321, 2341417168561, 2433603120001, 2512481776561, 2659277071441, 2675975777281, 2709608995921, 2760652033441, 2777825555761, 2829827119681, 2864898145201, 2882555400481, 2918114646001, 3026768337121, 3045168091681, 3100870943041, 3431093087041, 3491998578721, 3553711346641, 3637263079921, 3830635754401, 3941340648961, 4100337455041, 4146635796241, 4169931445681, 4216817073121, 4287885459841, 4384036128481, 4432713370801, 4457203441681, 4531282799761, 4682207873281, 4810832476321, 4836872105521, 4889268346561, 4915625528641, 4968659444401, 5049013494001, 5212641500641, 5380214781841, 5494153169521, 5668441960801, 5757125158801, 5816822652481, 5907237891361, 6029426229121, 6091226377681, 6216250684081, 6279479680321, 6504586067281, 6569999366401, 6669042837601, 6702304832161, 6769201929361, 6870484987921, 6904497224881, 7007291942641, 7181161893361, 7538588431201, 7648371893761, 7722224074321, 7759350084721, 8215383330001, 8293299876481, 8332465333201, 8530377503761, 8772502109281, 8813351875441, 9019744817521, 9187452028561, 9314758936081, 9443384314081, 9573337234561, 9971252437441, 10106606869921, 10197605570161, 10243334671441, 10520947447201, 10756569837841, 11044515642241, 11239665258721, 11637711365281, 11994592349041, 12150027804721, 12254487410881, 12306969080641, 12412437950641, 12465425870881, 12732914759041, 13059557667601, 13225215949201, 13392445265761, 13903658595121, 13961350047121, 14429369557201, 14488688572801, 15153339067441, 15338510106481, 15588038452561, 15777173258401, 15904215784081, 15968023992001, 16096216216081, 16354914662641, 16550975387521, 16881653995441, 16948379819281, 17284980865441, 17764614906481, 18113272128961, 18324914739121, 18753758574721, 18825957754321, 18970981313761, 19043806494241, 19411082451601, 19858796855041, 19934162223361, 20544834434881, 20622143227921, 20855379099361, 21011965022161, 21090587817601, 21487016597281, 21808162146241, 22543893337681, 23553637597681, 23725169980801, 23984223122161, 24332920331281, 25041707380561, 25131382160641, 25311454040401, 25674499134001, 26412291425521, 26505620986321, 26693021907841, 27070803167521, 27356759876161, 27644976106801, 27838381411681, 28424689653361, 28523300799841, 29625040666321, 29930976588241, 30033479838961, 30342569711281, 30549950894401, 30863013591601, 31602847532881, 31923957716641, 32139386443921, 32247508758721, 32573512997041, 32792218149601, 33122338550401, 33790050552241, 34127667088321, 34467807323041, 35271352782961, 35503495827361, 35853856620481, 36562351115761, 37040479315921, 37402141201441, 37644716109841, 39250337770081, 40391630304481, 41036336333521, 41557633003441, 41820135988801, 42216219754801, 42348870775201, 42748699986001, 44239006840081, 45068141784961, 45207455875201, 46333628948161, 46904541018721, 47191967468881, 48062176770721, 49092569678881, 49838644003201, 49988873418961, 50290350881761, 50897394646081, 51356271336241, 51818243883121, 52127952360961, 52283326179841, 52595115558001, 53065411729201, 53697370966801, 54015458929441, 54175031816161, 54655872347521, 55464377448481, 55627148806321, 56446386112561, 57108264114001, 57441377422081, 58618761251521, 59470764169441, 60505388947441, 60679130081761, 61202599057681, 61553455051201, 61729447662481, 63151010391121, 64414894240321, 64779462947761, 65329214857201, 66067651496401, 66625573677601, 66999479873041, 68701569626881, 69468374283361, 70435885826881, 71021222453281, 71610199722961, 72401192014321, 73399126194241, 74610224073841, 76042045003681, 76454895334801, 77077320038161, 77703537431521, 77913122039281, 80892053988001, 81108054012001, 82194549986641, 83071576438321, 83512712283841, 85070535710161, 85519603877761, 86423071552801, 87791671617841, 88482035307121, 89874969418081, 90342914902321, 91048256370241, 93429255506161, 94637116441921, 94880087090881, 96840734511361, 100091400875761, 100598673352321, 100853031438721, 102389324175121, 103164019266961, 103682919315361, 105251369305681, 106042233977761, 107103643129921, 107637325775281, 108710671926481, 111703782138001, 111978914476081, 112530703586401, 112807361608561, 114478037712481, 118448417326801, 118735913353201, 119601542190001, 120471895488961, 121346990409121, 121933029744241, 122816065582081, 123111473904721, 124895130571201, 125493967403281, 127303403660161, 127606868135041, 129132336776881, 129439064282641, 131912598473041, 132224264252161, 134737515307201, 135689159747761, 138897750969121, 141505323151201, 142822791820801, 143484965347441, 143816914232161, 144482539567921, 144816217349521, 148524943300561, 149891073486001, 151957912148641, 152999310365521, 154746857593441, 155098155653281, 155802545803921, 156863626279441, 157218521219761, 158286819901681, 160079404758001, 160439740923361, 162614549665681, 164443716720721, 164811393976321, 166659037303201, 169271783181601, 170400885105361, 171156751470721, 172295262524641, 173822101273921, 174973872717361, 176131358559601, 179246068134961, 181609071490081, 182005165283041, 182799296268241, 185599234557361, 186809002860481, 187618794154801, 189246272135761, 191295482183521, 192946795899841, 194192279513521, 195443783174641, 200084448104641, 201364301903521, 201792281140321, 203942419667281, 206981424148801, 207855915349681, 209172844170481, 213161197201681, 213607841778241, 215851602388321, 219022506749281, 219934861700401, 220392106580881, 222689034627361, 225934839014641, 226868693989921, 228745085711041, 233009509093201, 233965199238241, 235404242866321, 235885395990721, 236849914625041, 238302234835681, 238787822523121, 241716951468001, 242699289858481, 247655970193921, 253195594718641, 256256096016001, 256768864432081, 257796709490401, 259344259180561, 260898765874321, 261418484370481, 262982299459441, 268776384148801, 269307825181201, 270906877644001, 275205836670241, 276831063574081, 280103101710961, 280651248517201, 282300516843601, 285620849903041, 290093418272641, 290656159946881, 291784099092721, 293482159205041, 297473117213281, 298620829861201, 299195929992961, 304409289234241, 311466057856801, 314442301015441, 316238254381921, 316838611601521, 319853229882481, 320458725652321, 323499109738561, 324109773296401, 327176069584081, 329026259524561, 329644729766641, 332750169756481, 333373881243841, 336505601239921, 338395192861441, 340927013995681, 350548070339041, 353799885965761, 354452954340241, 357731868267601, 360371335935601, 362360501421361, 365694062750641, 371752372136161, 373788436964881, 377885645796961, 382016445748081, 382708191059041, 388976256795361, 391082621604481, 392491609582801, 394612225792801, 396741423620161, 403180738168321, 403901025149521, 407516947328401, 412619959676401, 414821573074561, 416294202017521, 417031985092321, 418510492785841, 427464267193681, 428216844946801, 432753201003841, 435034847385121, 441163353124321, 444251774352961, 446578710143281, 448914775136881, 455977983956881, 462326070129361, 463124215943041, 464723607387601, 467130457466401, 467934814503601, 470354119147201, 472782792857761, 476851468151041, 479305244227681, 484241194041361, 489215169367681, 496747856441281, 497590158679441, 500123493360481, 501817748861521, 509495229144001, 512935572982561, 523361201113921, 525114136406161, 525992253499441, 527751791176801, 530399370220801, 531284106259201, 536615788770961, 538401901773121, 544688429550721, 558344810921041, 562953493142881, 565732361546641, 571320949187041, 577893185069281, 580727147154961, 585473564226721, 591207602487121, 592167354891121, 594090364812961, 596983656696001, 600857802784801, 603775763278801, 608662632445921, 609643555103521, 611608956871441, 618525306088561, 621507343142401, 624500149980001, 626501350540081, 629512164586561, 630518176634641, 635566335414481, 636579593619841, 644729338693441, 650892809785201, 655026269697361, 664398515813041, 666494821866721, 669648577349761, 675989652039601, 677050860080401, 680241981939601, 683444370987361, 686658053713921, 701805347408881, 705083529521281, 712777277056321, 714987009256081, 719421883405681, 724994451369841, 729475763598481, 736236644609761, 746465946897841, 748753525216321, 749899284035521, 752194746016561, 766078382090641, 773091832911841, 776616562001281, 777794145659521, 787263092287681, 790836141432481, 794421339201361, 802834199880241, 808884167110321, 817411486787281, 819860199506401, 838401348535921, 842146992813361, 845905173633601, 849675918938401, 854723172451201, 858523343723761, 861063821644321, 862336172844721, 869999916969121, 873850888218961, 876425295279361, 877714629810001, 881591169943201, 895915105649281, 899851746105841, 901166837952481, 903801345497521, 915728181522001, 917060634094081, 919729901048401, 927772672528321, 929118245436481, 933163747057441, 935868077825521, 953589778302001, 957714890286961, 961853371365121, 964619800272241, 970170556248721, 977142648636961, 999706081460641, 1011133218419041, 1012568467616161, 1016883383954881, 1019767646307601, 1021212076175281, 1024105538719201, 1025554573566961, 1032822827028721, 1043063201727121, 1047475165407841, 1050424240242001, 1056341066962801, 1063772210101441, 1068249673759921, 1083276693622561, 1086301020364561, 1087815556238401, 1092368667102001, 1115348988779281, 1118440201861921, 1124641900133761, 1132430249863201, 1137122634120001, 1141829585958961, 1148128234489681, 1152869294537041, 1162395449154241, 1165583914141201, 1170378905061601, 1171980518108401, 1176795221193601, 1180013254445041, 1184852673612721, 1186469116315921, 1194576152894881, 1196202532717921, 1209273431102881, 1214202528377281, 1230741742361041, 1234069755990241, 1244094302301841, 1255866657127681, 1279661811514321, 1284804451300561, 1302058592234401, 1305530167958641, 1321238242043281, 1328264921546161, 1333553295586801, 1337087640631681, 1342402324938481, 1354864862463121, 1360232428806241, 1365615927886081, 1374623917998241, 1376430850278961, 1385492247284401, 1396424896575361, 1403749187822881, 1412945024683921, 1414789600188721, 1424039583129601, 1431472166709601, 1442675547839761, 1452061824953041, 1474775739090481, 1476680518615201, 1480495612429681, 1488147972463441, 1493906680885921, 1497755094107281, 1505474221794481, 1522951327450081, 1532726336702401, 1538613883078561, 1544518374730321, 1546490309844481, 1552417445731441, 1562333846324161, 1574296150114801, 1576296526165201, 1586327016495841, 1592368242351121, 1598426706948241, 1604502443050081, 1612630347989761, 1618746511855201, 1628978758850881, 1635141345008161, 1637199420707041, 1643385305838721, 1649588703686641, 1655809647272881, 1666216966901041, 1674578083148881, 1699850313436081, 1706212815456241, 1729694911339201, 1731841600390801, 1751251839857521, 1755587290273441, 1764282335296321, 1775196514552561, 1808243034480481, 1817132828321281, 1837254685777681, 1841748809191201, 1843998960192481, 1855280658474961, 1862074477401121, 1864343224597681, 1871161906511041, 1875718074012721, 1896323877333601, 1905536303697601, 1919417828167921, 1940382148953361, 1959160850483281, 1966237884282961, 1968601150704241, 1982825517887041, 1989966538939681, 2001911082483841, 2004306429009361, 2016315421366801, 2018723680783681, 2025961404083761, 2038067503691521, 2055107091557521, 2059995109834561, 2089506583076641, 2091980103472561, 2111847411335281, 2114340737405521, 2126840500817761, 2129347089232801, 2141913281694481, 2167212440982241, 2172299045669041, 2174845703128081, 2179945734832321, 2190172702116961, 2210734546365601, 2218482440391361, 2226250681951921, 2228844623630881, 2244455908224721, 2265398349632401, 2275924358809201, 2281201097610241, 2289133403422321, 2329105685334481, 2331788986537201, 2345240287037761, 2347937515381441, 2356043160949921, 2361458571815281, 2369599185603841, 2377760828519521, 2388675793594561, 2396886645244081, 2402372294028001, 2418885747544561, 2427174326182321, 2438258877655441, 2454956837245441, 2460541835614801, 2480164401960001, 2497076954919121, 2511236698042081, 2545465754906881, 2554077415970161, 2571366272066881, 2580043540868641, 2582940838214881, 2614972416513601, 2626693804140961, 2653210974030241, 2668029206514961, 2676949887084001, 2697851794840801, 2703846186187441, 2706847125062161, 2715864931109521, 2730944655750481, 2743053578440561, 2752161662180401, 2758246306342081, 2767392182908081, 2813463205483921, 2835158772871681, 2850732253278001, 2853854632233361, 2872642803955681, 2888370348960721, 2891523591406321, 2916842568855601, 2920019091914401, 2948724689269921, 2987327417289601, 3016527251172241, 3026307931348321, 3052506034761121, 3082181813794801, 3092121655708801, 3095440272695761, 3125428172769841, 3132121631860321, 3142181971618561, 3145540797584641, 3162375337470001, 3175891547792401, 3192847684973521, 3203053902789841, 3213284569877281, 3226963558964161, 3233819407955761, 3244123657069681, 3247563872734801, 3264806010987361, 3268262660775841, 3289060236408241, 3296014768643041, 3306467238568321, 3316944549312241, 3320442513204961, 3341488431860881, 3348525919869601, 3373244698688881, 3405226779371041, 3412364681871601, 3423092568854401, 3459034957500721, 3466257264755041, 3480735803013121, 3491624436420961, 3498897704493361, 3513478323709201, 3520785698491681, 3546451304263921, 3557493697483441, 3564869605227841, 3590775636532561, 3613092962962081, 3620555137760401, 3624290556730561, 3680669440327441, 3688236020260801, 3733880785929121, 3745357870050241, 3756861392284081, 3779947913400961, 3803140674212881, 3830333604516721, 3842032247888641, 3849846217142641, 3853757668406881, 3861589511772721, 3896980630491601, 3908831551381201, 3932614460934721, 3948529915854241, 3960498171735121, 3968492110248961, 3992546545933201, 3996566224996801, 4020748076978161, 4081682805026401, 4114463127334561, 4118574506606641, 4130927133299521, 4176457964521441, 4205627427954481, 4218175288245361, 4239150758955121, 4264424473158721, 4277103625385761, 4281336285750241, 4289811030229201, 4306798257692401, 4328103179999041, 4340924015004721, 4353773312630641, 4405455971684881, 4435815880890241, 4448875192612321, 4457597405788081, 4475080301473681, 4501401006735361, 4541099550557761, 4563267434945521, 4567710732995281, 4589975915908321, 4594438702079521, 4603374036652561, 4616801467808401, 4661771806654561, 4675326743602321, 4684379775915841, 4716168957548161, 4725281224343761, 4729842306274801, 4738974375163681, 4771040786343841, 4784833234455121, 4812507821362081, 4868216966666881, 4891571287773361, 4905624152905921, 4924408380908641, 4947964466049361, 4952685805853041, 5023912167552721, 5033466734531041, 5047824129937681, 5052616746861121, 5081444155494001, 5091080647572481, 5124916338967441, 5139468860827921, 5222519433534001, 5252070336226561, 5271840488568481, 5286704691253441, 5311548185576161, 5316527372659441, 5326496248156801, 5376551078850961, 5401710376476241, 5421901305540721, 5462452920911281, 5467537819725601, 5493015585644161, 5528833919864641, 5539099826666641, 5544238137848881, 5575143118268161, 5590643970230881, 5632137612809761, 5647757120736721, 5668633640928241, 5679093577977121, 5700056872635841, 5710560256926001, 5726342542105201, 5747436448798801, 5763295082144161, 5779186511363521, 5811067938190321, 5827058026258561, 5837736402616561, 5853781477180081, 5869859604070081, 5891348599724641, 5939914532447281, 5950747612105921, 6005135446710481, 6016057595436001, 6048913448607121, 6054402480421681, 6081903696606721, 6098449333019761, 6103972039782241, 6131641859649601, 6164969697017041, 6170537517567361, 6181684471968721, 6237645952755361, 6254508243531601, 6339333093965041, 6356401066615681, 6367798846683121, 6390640384473361, 6419278656400801, 6453771512366161, 6471069974447521, 6476843848703281, 6558084485964001, 6563916486036001, 6581435826350401, 6593134853930641, 6598990213120561, 6645973604711281, 6681375449981761, 6687289479670801, 6705055127128801, 6734743171761361, 6758564501619121, 6830407763130961, 6866543424722881, 6884664928202161, 6939244695932641, 6957509861832721, 6969706654983361, 7012521752121601, 7030931337721201, 7043224516014241, 7080200787557041, 7104932389959121, 7123523568138961, 7160815355803201, 7173278427553681, 7192003529873761, 7229563690439281, 7248398844225841, 7286179537892641, 7292490650158561, 7343127261818401, 7406793322927441, 7419576050315521, 7425973614979921, 7458023519302801, 7515974649267841, 7541838824625121, 7554795916152241, 7600277251025761, 7613309552826961, 7619831985139201, 7639424429247601, 7711586804240881, 7731355869440641, 7777631491556161, 7797527362424881, 7817461380455281, 7850769647675761, 7870805629788721, 7877492804968081, 7910992620825121, 7917705384657121, 7931143727466961, 7937869310067841, 8012133369691441, 8018910390560161, 8032477329079921, 8052860006077441, 8073281449776481, 8114240833804561, 8134778872474081, 8182852572092641, 8217321153612481, 8258827060291921, 8279638877935441, 8307449123653681, 8321380489003201, 8447552693903761, 8497005096998401, 8539565406633361, 8560905418075921, 8575154295332641, 8596560952604881, 8603705403457921, 8646665671527601, 8668206036446401, 8711407478076241, 8769260353860241, 8776512171007681, 8812838745711841, 8841981103812481, 8922495313199521, 8929841953661281, 8974017115601521, 8996166057230641, 9010954778750401, 9033172039086001, 9100070373815521, 9107526391756321, 9152358761897521, 9174836914466161, 9189845334869761, 9234981091218481, 9265163825229841, 9287849382033121, 9333345446596081, 9348547879276321, 9371386340658241, 9417188774924401, 9440152849881601, 9447816866414161, 9493899009362881, 9540149522868721, 9555603847167361, 9609841884099601, 9633157300525201, 9695539173833041, 9719010308971681, 9726843482307121, 9766080396957361, 9797555300725201, 9868651963705921, 9892436613211441, 10028029413722401]
ans = 0
n = int(input())
tmp = n
for s in sosu:
    if n%s == 0:
        ans += 1
        n /= s
    if n < 2:
        break
if tmp == 1:
    print(0)
else:
    if ans == 0:
        print(1)
    else:
        print(ans)