C. Dirichlet's Theorem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A famous theorem in number theory says: for any two positive integers $$$a, b$$$ with no common factors, there are infinitely many primes $$$p$$$ of the form $$$p = ax + b$$$ (for $$$x$$$ an integer).

For example, here are some primes of the form $$$4x + 1$$$: $$$5, 13, 17, 29, 37, \ldots$$$.

Here are some primes of the form $$$4x + 3$$$: $$$3, 7, 11, 19, 23, 31, \ldots$$$.

There is only one prime of the form $$$4x + 2$$$, but that is not a counterexample since $$$4$$$ and $$$2$$$ have a common factor.

You would like to check the plausibility of the above theorem computationally. Given $$$a$$$ and $$$b$$$, how many of the primes less than ten million are of the form $$$ax + b$$$?

Input

The only line of input contains two space-separated integers $$$a$$$ and $$$b$$$. They satisfy the bounds $$$1 \leq b \lt a \leq 10^4$$$. It is guaranteed that $$$a$$$ and $$$b$$$ are relatively prime (share no common factors).

Output

Print the number of primes less than ten million of the form $$$ax + b$$$ (for $$$x$$$ an integer).

Examples
Input
4 1
Output
332180
Input
4 3
Output
332398
Input
10000 9999
Output
168