Let $N$ be the original integer John selects. Mary's First Try: $d=2$. If $N$ is even, she wins. If not, the new integer is $N-2$. Mary's Second Try: $d=3$. If $3 \mid N+1$, she wins. Otherwise, $3 \nmid N+1$ and $N$ is odd. The new integer is $N-5$. Mary's Third Try: $d=4$. If $4 \mid N-1$, she wins. Otherwise, $N$ is odd such that $4 \mid N+1$ and $3 \nmid N+1$. The new integer is $N-9$. Mary's Forth Try: $d=6$. If $3 \mid N$, she wins. Otherwise, $N \equiv 7 \pmod{12}$. The new integer is $N-15 \equiv 4\pmod{12}$. Mary's Fifth Try: $d=16$. She will fail this time, but the new integer becomes $N-31 \equiv 0\pmod{12}$. Mary's Final Try: $d=12$. She will definitely win as $12 \mid N-31$.