Let p_{n} be the nth prime number (starting at 0): p_{0} = 2, p_{1} = 3, p_{2} = 5, p_{3} = 7, … Define r_{n} as the remainder of (p_{n} + 1 ) ^{n} + (p_{n} − 1 )^{n} modulo (p_{n})^{2}. For instance, r_{3} = 42, because
(7+1)^{3} + (7−1)^{3} = 512 + 216 = 728 = 14 · 49 + 42 . |
Given two integer numbers a and b, find the largest r_{i} 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 p_{b} ≤ 10^{7}.
Output
For every case, print the largest r_{i} such that i ∈ [ a, b ].
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