Counting Lehmer generators

Let a Lehmer generator xn+1 = R*xn mod M be represented by tuple (M, R). It is known that its period is maximal if M is a prime and R is a primitive root modulo M.
For a positive integer K, let PF(K) be the set of all prime factors of K. A primitive root R modulo M can be characterized in two ways:

  1. Every positive integer less than M is congruent to some power of R modulo M. This is the standard definition.
  2. R(M−1)/p is not congruent to 1 mod M for all p ∈ PF(M−1).
The second characterization is useful for a fast computational test whether a given number is a primitive root modulo M. We can see that it can be evaluated quickly especially when PF(M−1) consists of a small number of primes. Based on empirical observations, the existence of a primitive root R modulo M with a value very small relative to M can also be expected in this case.

The task

For given two integers Mmax and D, find all Lehmer generators (M, R) satisfying

Input

The input consists of one line which contains integers Mmax and D separated by space.
It holds 3 ≤ Mmax ≤ 4×1014 and 3 ≤ D ≤ 40.

Output

The output consists of one line containing integers L and Rmax separated by space, where L is the number of feasible Lehmer generators and Rmax is the maximum among their primitive roots R.

Example 1

Input
10 3
Output
3 3
The three feasible Lehmer generators are as follows:

Example 2

Input
20 5
Output
7 3
The seven feasible Lehmer generators are as follows:

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