【题目描述】

有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