• String

 

时间限制:1s

空间限制:512MB

 

题目描述

 

现有一个整数序列A,将其复制无限份放在自身后面,即变成AAAA......的形式,记这个无限序列为B。

我们想要把B复制若干份,与原来的B重叠在一起,但要求新B序列的开头必须在第一个B序列的第一个循环节内。

例如A=[1,2,3]时,我们可以这样复制重叠成一个表格:

1

2

3

1

2

3

...

 

 

 

1

2

3

1

2

3

...

 

 

 

1

2

3

1

2

3

...

这样算上最开始的B,一共可以放三个重叠在一起。

不能再放入第四个B了,因为如果放入第四个B,则第四个B的开头一定不在第一个B的第一个循环节内。

现在有一个额外要求,在这个无限表格中,任选两个横行,在所有这两横行都有数字的列上,这两个数字的差必须都是a的倍数,或者都是b的倍数。

求表格最多可以有多少行(也即最多有多少个B可以重叠)。

 

输入格式

 

本题包含多组输入。

第一行包含一个整数T,表示数据组数。

每组数据的第一行包含三个整数n,a,b,n代表序列A的长度,a,b的含义见题目描述。

每组数据的第二行包含n个整数,第i个数a_i代表序列A的第i项。

 

输出格式

 

对于每组数据,输出表格最多可以有多少行(也即最多有多少个B可以重叠)。特别地,如果只能有一个B序列(也就是最开始的B序列)而不能有其他重叠的话,输出0。

 

样例输入

 

2

3 1 1

1 2 3

5 2 6

1 4 7 4 1

 

样例输出

 

3

0

 

数据范围

 

对于20%的数据,n<=16。

对于40%的数据,n<=100。

对于60%的数据,n<=1,000。

对于80%的数据,n<=100,000。

对于50%的数据,a=b。

对于100%的数据,1<=n<=1,000,000,1<=a,b<=1,000,000,000,0<=a_i<=1,000,000,000,0<=t<=3。