P.J. starts with $m=500$ and chooses a positive integer $n$ with $1 \leq n \leq 499$. He applies the following algorithm to $m$ and $n$ :

- P.J. sets $r$ equal to the remainder when $m$ is divided by $n$.
- If $r=0$, P.J. sets $s=0$.

If $r>0$, P.J. sets $s$ equal to the remainder when $n$ is divided by $r$.

- If $s=0$, P.J. sets $t=0$.

If $s>0$, P.J. sets $t$ equal to the remainder when $r$ is divided by $s$.

For example, when $n=8$, P.J. obtains $r=4, s=0$, and $t=0$. For how many of the positive integers $n$ with $1 \leq n \leq 499$ does P.J.'s algorithm give $1 \leq r \leq 15$ and $2 \leq s \leq 9$ and $t=0$ ?
(A) 14
(B) 12
(C) 16
(D) 15
(E) 13
Suppose that $m=500$ and $1 \leq n \leq 499$ and $1 \leq r \leq 15$ and $2 \leq s \leq 9$ and $t=0$.

Since $s>0$, then the algorithm says that $t$ is the remainder when $r$ is divided by $s$.

Since $t=0$, then $r$ is a multiple of $s$. Thus, $r=a s$ for some positive integer $a$.

Since $r>0$, then the algorithm says that $s$ is the remainder when $n$ is divided by $r$.

In other words, $n=b r+s$ for some positive integer $b$.

But $r=a s$, so $n=b a s+s=(b a+1) s$.

In other words, $n$ is a multiple of $s$, say $n=c s$ for some positive integer $c$.

Since $n>0$, then $r$ is the remainder when $m$ is divided by $n$.

In other words, $m=d n+r$ for some positive integer $d$.

But $r=a s$ and $n=c s$ so $m=d c s+a s=(d c+a) s$.

In other words, $m$ is a multiple of $s$, say $m=e s$ for some positive integer $e$.

But $m=500$ and $2 \leq s \leq 9$.

Since $m$ is a multiple of $s$, then $s$ is a divisor of 500 and so the possible values of $s$ are $s=2,4,5$.

(None of $1,3,6,7,8,9$ is a divisor of 500 .)

We know that $r$ is a multiple of $s$, that $r>s$ (because $s$ is the remainder when $n$ is divided by $r$ ), and that $1 \leq r \leq 15$.

If $s=5$, then $r=10$ or $r=15$.

If $s=4$, then $r=8$ or $r=12$.

If $s=2$, then $r=4,6,8,10,12,14$.

Suppose that $s=5$ and $r=10$.

Since $m=d n+r$, then $500=d n+10$ and so $d n=490$.

Therefore, $n$ is a divisor of 490 , is a multiple of 5 (because $n=c s$ ), must be greater than $r=10$, and must be 5 more than a multiple of 10 (because the remainder when $n$ is divided by $r$ is $s$ ).

Since $490=5 \times 2 \times 7^{2}$, then the divisors of 490 that are multiples of 5 are $5,10,35,70,245,490$ (these are 5 times the divisors of $2 \times 7^{2}$ ). Among these, those greater than $r=10$ having remainder 5 when divided by 10 are 35 and 245, and so the possible values of $n$ in this case are 35 and 245 .

For each possible pair $s$ and $r$, we determine the values of $n$ that satisfy the following conditions:

- $n$ is a divsior of $500-r$,
- $n$ is a multiple of $s$,
- $n$ is greater than $r$, and
- the remainder when $n$ is divided by $r$ is $s$.

We make a table:

| $s$ | $r$ | $500-r$ | Divisors of $500-r$  that are multiples of $s$ | Possible $n$ |
| :---: | :---: | :---: | :---: | :---: |
| 5 | 10 | $490=5 \times 2 \times 7^{2}$ | $5,10,35,70,245,490$ | 35,245 |
| 5 | 15 | $485=5 \times 97$ | 5,485 | 485 |
| 4 | 8 | $492=4 \times 3 \times 41$ | $4,12,164,492$ | $12,164,492$ |
| 4 | 12 | $488=4 \times 2 \times 61$ | $4,8,244,488$ | 244 |
| 2 | 4 | $496=2 \times 2^{3} \times 31$ | $2,4,8,16,62,124,248,496$ | 62 |
| 2 | 6 | $494=2 \times 13 \times 19$ | $2,26,38,494$ | $26,38,494$ |
| 2 | 8 | $492=2 \times 2 \times 3 \times 41$ | $2,4,6,12,82,164,246,492$ | 82 |
| 2 | 10 | $490=2 \times 5 \times 7^{2}$ | $2,10,14,70,98,490$ | None |
| 2 | 12 | $488=2 \times 2^{2} \times 61$ | $2,4,8,122,244,488$ | 122 |
| 2 | 14 | $486=2 \times 3^{5}$ | $2,6,18,54,162,486$ | None |

In each row, we calculate the prime factorization in $500-r$ in the third column, list the divisors of $500-r$ that are multiples of $s$ in the fourth column, and determine which of these are greater than $r$ and give a remainder of $s$ when divided by $r$ in the fifth column.

Therefore, the possible values of $n$ are $35,245,485,12,164,492,244,62,26,38,494,82,122$, of which there are 13 .

ANswer: (E)