有N个学生，学生编号从0至N-1，第个学生有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行，每行一个整数。

5
10 12345678 0
10 1 0
10 12345678 3
10 10 4
100000 7 0

1
10
4
6
28572