Primes and moduli P45675


Statement
 

pdf   zip

html

Let pn be the nth prime number (starting at 0): p0 = 2, p1 = 3, p2 = 5, p3 = 7, … Define rn as the remainder of (pn + 1 ) n + (pn − 1 )n modulo (pn)2. For instance, r3 = 42, because

(7+1)3 + (7−1)3   =   512 + 216   =   728   =   14 · 49 + 42   .

Given two integer numbers a and b, find the largest ri such that i ∈ [ a, b ].

Input

Input consists of several cases, each one with two integer numbers a and b, where 0 ≤ a ≤ b and pb ≤ 107.

Output

For every case, print the largest ri such that i ∈ [ a, b ].

Public test cases

  • Input

    1 1
2 2
1 2
3 3
1 10
1 100
1 1000
600000 600002

    Output

    6
2
6
42
522
107118
15822162
10752590320954
    • Information
    Author
    Albert Graells
    Language
    English
    Official solutions
    C++
    User solutions
    C++