We need k square pieces cut from a rectangular piece of paper with length a and width b. Here we assume a is greater than b. Obviously, the biggest side length of a square we can get is b, so the length a of the rectangular piece must be greater than k × b. And after k squares got, the rest part of original rectangle should be a rectangular piece with length b and width c = a - b × k. Here we assume b is not less than c, or we will waste too much. To reuse the rest part, we want the rest rectangle is similar to the original rectangle, but it is impossible (can you prove?).
To measure how similar is the rest rectangle to the original rectangle, we define best(b) = min {abs( b ÷ ( x - k × b ) - x ÷ b ) | for x ≥ k × b}. We call b is a good width if best(b) is less than best(d) for any positive d less than b. And if a rectangle with a good width b and a length a which makes abs(b ÷ (a - k × b) - a ÷ b) minimal, it is a good rectangle. We can get the result easily for each good width, a good rectangle can be got. And we sort the good rectangles by its width from small to large. Now given k, can you calculate area of the nth good rectangle? (all variables above is integer)
Input
There are no more than test cases. Each test case has only one line, containing two integers k and n (0 < k < 1000001, 0 < n < 1000001).
Output
Output one line for each case, each case need only a number contained one integer S, which indicates the area of the nth good rectangle. S may be very large, so print S MOD 9875321.
Sample Input
1 10
2 1
Sample Output
12816
3
