2418: 卡农
题目描述
今天我们最熟悉 的卡农作 品是 帕赫贝 尔的《D大调卡农》 ，也称作《帕赫贝尔的卡农》。其曲谱例子如图(1)所示 。
Figure 1: 帕赫贝尔的卡农。在曲谱中，第一行（Violin 1）是导句，我们称它为首声部；第二行（Violin 2）是答句，我们称它为二声部；第三行（Violin 3）是另一个答句，我们称它为三声部 。三把小提琴形成三个声部间隔八拍先后加入。小提琴全部拉奏完全相同旋律，音乐悦耳动听。
柳德米拉也想谱一曲优美的卡农，在聚会的时候不停地演奏。她写了一个旋律，然后尝试把它变成卡农。柳德米拉写的曲子很简单，都是由四分音符构成的（这样每个音的持续的时间都一样，另外一个四分音符的音长就是一拍）。由于她不会转调等比较复杂的技法，她就希望她的音乐的导句和若干答句一模一样，都是她谱写的旋律的不断重复，只不过每个答句形成的声部比前一个进入的声部 （导句或答句）晚若干拍开始。当然，每个答句都要在导句奏完第一遍旋律之前开始。
柳德米拉发现，虽然她写的旋律很动听，但是将它随意变成一个卡农后，就不是很优美了。她苦思冥想，觉得是这样一个因素作怪 。
如果某个时刻，有两个及以上的音在响，有些音的组合很和谐，而有些就不和谐。柳德米拉发现，如果两个声部，在相同时刻演奏的音高的差，全都是a的倍数，或者全都是b的倍数，那么它们就是优美组合。
进一步的研究表明，多个声部一起演奏不会显得难听，当且仅当任何两个声部 ，它们都是优美组合。柳德米拉做了一些实验，得到了神奇的数字a和b。现在就请你为她得出她的卡农吧 ！
输入
输出
样例输入 复制
2
3 1 1
1 2 3
5 2 6
1 4 7 4 1
样例输出 复制
3
0
提示
【样例解释】
在第一组数据中，第一个答句在导句演奏完1拍后开始，第二个答句在导句演奏完2拍后开始。可以发现，对于任意两个声部，它们同时演奏的时候，音高差都是1的倍数。又因为每个答句都要在导句奏完第一遍旋律之前开始，所以3就是最大值。
谱出的曲子表示如下：
首声部 （导句）： 1 2 3 1 2 3. . .
二声部 （答句）： 1 2 3 1 2 3. . .
三声部 （答句）： 1 2 3 1 2 3. . .
【数据范围及约定】
对于20%的数据，n<=16
对于40%的数据，n<=100
对于60%的数据，n<=1000
对于80%的数据，n<=10^5
有50%的数据，a=b
对于100%的数据，1<=n<=10^6,1<=a,b<=10^9,0<=h[i]<=10^9,0<=t<=3