Problem Description
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.
Input
The first line contains an integer $T(1 \leq T \leq 1000)$, indicating the number of test cases.
Each test case has one line, which contains two integers $x, y(2 \leq x_0, y_0 \leq 10^{12})$, indicating the position of the start point. It is guaranteed that $\gcd(x_0,y_0) > 1$.