#P18128. The Whole World

The Whole World

The Whole World

如果一个实系数多项式 f(x)f(x) 在所有整数点处都取整数值,则称它是整值多项式。

给定 nn 个整数点对 (xi,yi)(x_i,y_i)。求一个整值多项式 ff,使得

f(xi)=yi(1≤i≤n),f(x_i)=y_i\qquad(1\le i\le n),

并最小化它的次数。

本题把零多项式 f(x)=0f(x)=0 的次数定义为 00。

输入格式

第一行包含测试用例数 TT,满足 1≤T≤1001\le T\le100。

每组数据第一行包含整数 nn,满足 1≤n≤301\le n\le30。

接下来 nn 行,每行包含两个整数 xi,yix_i,y_i,满足

1≤xi≤30,−109≤yi≤109.1\le x_i\le30,\qquad -10^9\le y_i\le10^9.

保证同一组数据中的 xix_i 两两不同。

输出格式

对于每组数据,输出一个整数,表示最小可能次数。

样例

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