如果一个实系数多项式在所有整数点上的取值均为整数，我们称其为“整值多项式”（whole polynomial）。

给定 $n$ 对整数 $(x_i, y_i)$，你需要找到一个整值多项式 $f$，使得对于所有的 $i = 1, 2, \dots, n$，都有 $f(x_i) = y_i$，并求出该多项式可能的最小次数。

在本题中，多项式 $f(x) = 0$ 的次数视为 0。

输入格式

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

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 30$)，表示点的数量。

接下来 $n$ 行，每行包含一对整数 $(x_i, y_i)$ ($1 \le x_i \le 30, -10^9 \le y_i \le 10^9$)。保证所有的 $x_i$ 两两不同。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示该测试用例的答案。

样例

样例输入 1

2
2
1 0
4 1
3
1 1
4 4
6 6

样例输出 1

3
1