给你一个简单多边形，在给出多边形的 $n$ 个顶点之前，Little Q 还没有打乱它们的顺序，所以放轻松。

Little Q 会进行 $n$ 次询问，每次询问包含两个整数 $p$ 和 $q$ ($0 \le p/q \le 1000, 1 \le q \le 1000$)。

对于每次询问，你需要告诉他直线 $x = p/q$ 上位于多边形内部或边界上的点的总长度。该长度可以用两个整数 $r$ 和 $s$ 表示为 $r/s$ ($r \ge 0, s \ge 1, \gcd(r, s) = 1$)。其中 $\gcd(r, s)$ 是 $r$ 和 $s$ 的最大公约数。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($3 \le n \le 1000$)，表示多边形的顶点数。

接下来 $n$ 行，每行包含两个整数 $x$ 和 $y$ ($0 \le x, y \le 1000$)，按逆时针顺序给出多边形顶点的坐标 $(x, y)$。

接下来一行包含一个整数 $n$，表示询问的次数。

接下来 $n$ 行，每行包含两个整数 $p$ 和 $q$ ($0 \le p/q \le 1000, 1 \le q \le 1000$)，表示一次询问。

该多边形是简单多边形，即其顶点互不相同，且多边形的任意两条边不相交或接触，除了相邻边在公共顶点处接触外。此外，没有两条相邻边是共线的。

保证所有测试用例的 $n$ 之和不超过 $1000$。

输出格式

对于每次询问，输出一行，包含两个整数 $r$ 和 $s$ ($r \ge 0, s \ge 1, \gcd(r, s) = 1$)，表示询问的答案。

样例

输入格式 1

2
4
0 0
1 1
3 0
1 3
4
0 1
1 1
2 1
3 1
3
0 0
1000 999
999 1000
3
1 1
1999 2
1000000 1000

输出格式 1

0 1
2 1
1 1
0 1
1999 999000
1999 2000
0 1