• String

时间限制：1s

空间限制：512MB

题目描述

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

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

例如A=[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。