有N个学生，学生编号从0至N-1，第i个学生有a[i]个苹果，其中a[i]=1+(i*i%M)，注意：i*i可能比较大。有T次操作，每次操作你可以选择一个学生，然后吃掉该学生的若干个苹果(甚至可以全部吃掉)，你的目标是：T次操作结束之后，有尽量多的学生的苹果数量相同， 输出最多有多少个学生的苹果数量相同。

多组测试数据。

第一行，一个正整数G,表示有G组测试数据。1<=G<=5。

第二行，3个整数: N, M, T。 1<=N<=300000, 1<=M<=1000000000, 0<=T<=N。

共G行，每行一个整数。