Knights and Liars#10710
Every year, King Arthur conducts a certification for knights. He is very wise and therefore knows that there are only two types of people: knights and liars. Knights always tell the truth, and liars always lie.
This year, people came to the king. To find out who is truly a knight, the king numbered the people from to and called them to him one by one. The first person said that all people with numbers divisible by are liars, the second said that all people with numbers divisible by are liars, , the (n-1)-th person said that all people with numbers divisible by are liars, and the -th person said nothing.
Arthur wants to know what is the minimum and maximum number of knights that can be among the certified people.
The first line contains two integers and (3 \leq n \leq 10^{5}, 0 \leq k \leq 1) — the number of certified people and the query type. If k=0, then Arthur wants to know the minimum number of knights, if k=1, then the maximum.
In a single line, print one integer — the answer to the king's query.
Example 1
Example 2
Solutions that work correctly for n\leq 20 will score at least of points.
Solutions that work correctly for n\leq 5000 will score at least of points.
Solutions that work correctly for one type of query will score at least of points.