Notice：Don't output extra spaces at the end of one line.
Dodo bird is jogging on an infinite 2-d plane, starting from $(x_0, y_0)$. For a point$(x, y)$, it is regarded as good if and only if $\gcd(x,y)>1$.
Dodo bird will walk infinite steps on the plane under the following strategy:
Assume he is currently at $(x, y)$, let $S$ be the set of good points among $(x-1,y-1),(x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)$, $z$ be the size of $S$. He has a probability of $\frac{1}{z+1}$ to stay in $(x, y)$, and he also has a probility of $\frac{z}{z+1}$ to move to a point in $S$. If he chooses to move, the probility of going to any point in $S$ is equal.
Define $p_t$ as the probability of coming back to $(x_0, y_0)$ after walking $t$ steps, please calculate $\lim_{t \to \infty}p_t$. It is guaranteed that the answer always exists.