I. Luke's Math Problem
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Luke likes math problems, so he has asked you to solve this problem.

Given a vector $$$\langle x,y \rangle$$$, what is the total number of nonempty sequences of vectors $$$\{a_i\}_{i=0}^n$$$ such that:

  • $$$a_0 = \langle x,y \rangle$$$.
  • $$$\forall i \gt 0, i \in \mathbb{Z}, ||a_i||_2 \lt ||a_{i-1}||_2$$$.
  • $$$\forall i \gt 0, i \in \mathbb{Z}, ||a_i - a_{i-1}||_2 \lt \sqrt{2}$$$.
  • All vectors in $$$\{a_i\}$$$ have only integer entries.

Moreover, he will give you $$$Q$$$ queries, and you need to output the answer for each of these $$$\mod 10^9 + 7$$$ (a prime).

Note that for vector $$$v$$$ of dimension $$$n$$$, $$$||v||_2 = \sqrt{\sum_{i=1}^n v_i^2}$$$.

Input

An integer $$$Q$$$, $$$1 \leq Q \leq 10^6$$$ which gives the number of queries. $$$Q$$$ lines follow, each with two space separated integers $$$x_i$$$ and $$$y_i$$$, $$$0 \leq |x_i|, |y_i| \leq 10^6$$$, representing the $$$i$$$th query.

Output

On the $$$i$$$th line output the total number of nonempty sequence of vectors that satisfy the above properties for $$$\langle x_i,y_i \rangle$$$.

Example
Input
4
0 2
0 -1
0 -2
-3 -4
Output
3
2
3
125