Problem B
Blobs of Doom
The Mischievous Troublemakers’ Association (MTA) has hatched a sinister plot for world domination! All through the night, the Troublemakers work tirelessly, arranging rocks in the shape of hideous, misshapen blobs on the lawns of the unsuspecting residents of Quackville. For the sake of efficiency, the MTA splits up into several factions, each of which covers a particular neighbourhood. The faction in charge of spreading doom to a given neighbourhood never visits the same lawn twice. While there is no consistency whatsoever as to the shapes of the evil rock blobs, the MTA is very specific about the number of rocks each blob should contain. In order to generate this number easily, the $k^{\mathrm{th}}$ faction ($k \geq 1$) has devised a sequence, $F_ k(n)$, whose $n^{\mathrm{th}}$ term ($n \geq 1$) is the number of rocks its members will use to make their blob on the $n^{\mathrm{th}}$ lawn they visit. This sequence can be defined recursively by
\begin{align*} F_ k(1) & = 42\\ F_ k(2) & = 11k + 77\\ F_ k(n) & = 2F_ k(n - 1) - F_ k(n - 2) + 10k \, , \ \textrm{ for } n > 2 \end{align*}So, for example, the members of the first faction ($k = 1$) place $42$ rocks on the first lawn they visit, $88$ rocks on the second lawn they visit, then $144$, $210$, $286$, and so on, on subsequent lawns.
While others stare confusedly at the amorphous piles of rocks, wondering what any of this has to do with world domination, Rex Tangleton leaps into action! Despite a complete lack of evidence, he is convinced that Quackvillians can only be saved if someone turns these ghastly blobs of doom into wonderful rectangles. According to Rex, a $p$ by $q$ rectangle of rocks is wonderful if $p$ and $q$ are prime. Note that he does not care whether or not $p$ and $q$ are equal. For each lawn that he visits, he will rearrange all of the rocks in the blob into a wonderful rectangle if this is possible. Otherwise, he will simply stare at the rocks and grunt, but not move any of them.
Originally, Rex had been planning to check as many lawns as possible. However, he has been informed that his grunting frightens people, and he will therefore not be paid for his work. Saving your community is no fun if you do not get remunerated, so Rex decides to pick random positive integers $k$ and $n$, and then check only the first $n$ lawns that the $k^{\mathrm{th}}$ faction has visited. Rex wants to know how much work lies ahead of him, so he has asked you to write a program that, given $k$ and $n$, will determine on how many lawns he will rearrange rocks.
Input
The input consists of one line with two space-separated positive integers, $k$ and $n$. It is guaranteed that $k \leq 100$ and $n \leq 1\, 000\, 000$.
Output
Output a single non-negative integer giving the number of lawns that Rex will visit on which he will rearrange rocks.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 5 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 12 |
2 |
