Sequence Periods of Some Blum Blum Shub Random Number Generators

A Blum Blum Shub random number generator is an abstract or a physical device which produces a sequence of integers
     (x₀, x₁, x₂, x₃, ... ),    where
         x_i+1 ≡ x_i² mod M, (i ≥ 0),
         x₀ and M are coprimes,
         M is a product of two primes p, q each of which is congruent to 3 (mod 4).
Number x₀ is called seed of the generator, number M is called modulus of the generator.
The longest contiguous subsequence (x_k, x_k+1, ... x_k+r) (k ≥ 0, r > 0) of (x₀, x₁, x₂, x₃, ... ) which does not contain any value twice and in which the index k is the smallest possible is called sequence period. The length of the sequence period (or period length) is equal to the number of elements in it.
The period length of a sequence produced by a Blum Blum Shub generator is closely related to Carmichael function λ introduced below.

Let an integer n (n > 1) be expressed by its prime factorization
    n = p₁^e₁p₂^e₂ ... p_k^e_k,    where p₁, p₂, ..., p_k are pairwise distinct primes, e₁, e₂, ..., e_k are positive integes, 1 ≤ k.
Then Carmichael function λ(n) is defined as
    λ(n) = LCM[λ(p₁^e₁), λ(p₂^e₂), ..., λ(p_k^e_k)],    where, for each 1 ≤ i ≤ k,
         λ(p_i^e_i) = 2^e_i−2                  if p_i = 2 and e_i > 2,
         λ(p_i^e_i) = p_i^e_i−1(p_i−1)       otherwise.
For example,
     λ(7920) = λ(2⁴·3²·5·11) = LCM[λ(2⁴), λ(3²), λ(5¹), λ(11¹)] = LCM[2⁴⁻², 3²⁻¹(3−1), 5⁰(5−1), 11⁰(11−1)] = LCM[4, 6, 4, 10] = 60.

The period length of a sequence generated by a Blum Blum Shub generator with seed x₀ and modulus M is equal to the smallest positive integer D which satisfies both following conditions:
     1. λ(λ(M)) ≡ 0 mod D,
     2. x₁^{2D mod λ(M)} ≡ x₁ mod M,     where x₁ ≡ x₀² mod M.

In this problem, we are going to investigate a particular kind of Blum Blum Shub generator. We say a Blum Blum Shub random number generator with seed x₀ and modulus M is an
experimental Blum Blum Shub generator, denoted by BBSe(M), if all of the following holds:
     1. GCD(p−1, q−1) = 2,
     2. ⌊log₁₀(p)⌋ = ⌊log₁₀(q)⌋  (the number of decimal digits in p and q is the same),
     3. x₀ = (p + q)/2.

The task

Determine the period length of an experimental Blum Blum Shub random number generator.

Implementation remark

You may consider utilizing specific algorithms of modular arithmetic, namely modular multiplication and modular exponentiation by squaring.

---

Input

The input consists of a single text line which contains two positive integers M₁, M₂ separated by space.
It holds, 1 < M₁ < M₂ < 10¹⁴, M₂ − M₁ ≤ 10⁶.

Output

The output is one line with a single integer representing the sum of period lengths of all experimental BBS generators in the form BBSe(M), where M₁ ≤ M ≤ M₂. It is quaranteed that the output value does not exceed 10¹⁸.

Example 1

Input

20 30

Output

2

There is exacly one BBSe with M in the given input range, it is BBSe(21) with M = 3·7. It produces sequence (5, 4, 16, 4, ... ), which period starts with 4.

Example 2

Input

700 900

Output

118

There are four BBSe's with M in the given input range, BBSe(713), BBSe(737), BBSe(869), BBSe(893), which respective parameters and generated sequences are
     M = 713 = 23·31, period length = 20,
    (27, 16, 256, 653, 35, 512, 473, 560, 593, 140, 349, 591, 624, 78, 380, 374, 128, 698, 225, 2, 4, 16, ...),
     M = 737 = 11·67, period length = 20,
    (39, 47, 735, 4, 16, 256, 680, 301, 687, 289, 240, 114, 467, 674, 284, 323, 412, 234, 218, 356, 709, 47, ...),
     M = 869 = 11·79, period length = 12,
    (45, 287, 683, 705, 826, 111, 155, 562, 397, 320, 727, 177, 45, ...),
     M = 893 = 19·47, period length = 66,
    (33, 196, 17, 289, 472, 427, 157, 538, 112, 42, 871, 484, 290, 158, 853, 707, 662, 674, 632, 253, 606, 213, 719, 807, 252, 101, 378, 4, 16, 256, 347, 747, 777, 61, 149, 769, 195, 519, 568, 251, 491, 864, 841, 25, 625, 384, 111, 712, 613, 709, 815, 726, 206, 465, 119, 766, 55, 346, 54, 237, 803, 63, 397, 441, 700, 636, 860, 196, ...).

Example 3

Input

6000 12000

Output

164

There are only two BBSe's with M in the input given range, BBSe(6557) and BBSe (11021) listed below. Note the different number of digits in p and q in the generators.
     M = 6657 = 79·83, period length = 60,
     (81, 4, 16, 256, 6523, 1156, 5265, 3786, 194, 4851, 5685, 6329, 6085, 6403, 4045, 2310, 5259, 6212, 999, 1337, 4065, 585, 1261, 3327, 713, 3480, 6178, 5944, 2020, 1946, 3527, 1100, 3512, 427, 5290, 5381, 6006, 1979, 1912, 3495, 5891, 4237, 5660, 4655, 4697, 4061, 866, 2458, 2767, 4270, 4440, 3258, 5338, 4079, 3132, 152, 3433, 2560, 3157, 9, 81, ...),
     M = 11021 = 103·107, period length = 104,
     (105, 4, 16, 256, 10431, 6449, 7368, 8999, 10714, 6081, 3106, 3861, 6929, 3565, 2012, 3437, 9478, 313, 9801, 565, 10637, 4183, 7162, 2510, 7109, 6596, 7329, 8908, 1264, 10672, 570, 5291, 1341, 1858, 2591, 1492, 10843, 9642, 6029, 1583, 4122, 7523, 2694, 5818, 3633, 6552, 1909, 7351, 1238, 725, 7638, 4891, 6311, 9848, 9325, 10956, 4225, 7626, 9080, 9320, 5899, 4904, 1394, 3540, 723, 4742, 3724, 3758, 4663, 10157, 8089, 244, 4431, 5360, 8874, 2831, 2294, 5419, 5617, 8587, 6079, 828, 2282, 5612, 7547, 681, 879, 1171, 4637, 10819, 7741, 1904, 10328, 6346, 982, 5497, 8448, 7729, 3621, 7672, 7444, 10569, 5926, 4570, 105, ...).

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set