#P18128. The Whole World
The Whole World
The Whole World
如果一个实系数多项式 在所有整数点处都取整数值,则称它是整值多项式。
给定 个整数点对 。求一个整值多项式 ,使得
并最小化它的次数。
本题把零多项式 的次数定义为 。
输入格式
第一行包含测试用例数 ,满足 。
每组数据第一行包含整数 ,满足 。
接下来 行,每行包含两个整数 ,满足
保证同一组数据中的 两两不同。
输出格式
对于每组数据,输出一个整数,表示最小可能次数。
样例
2
2
1 0
4 1
3
1 1
4 4
6 6
3
1