1598: 水晶球

　　很久很久以前，有一个叫小猫猫的女巫，她用自己的法力制作了 n (1 ≤ n ≤ 1,000,000,000) 个水晶球。一旦这些水晶球被连起来，它们将会产生一股令人难以想象的力量。为防止别有用心的人使用这些水晶球，小猫猫又制作了 f (1 ≤ f ≤ 1,000,000,000)个外表和之前的一样，但是没有任何法力的水晶球，并把这些水晶球放在了一起。
　　大魔头飞猪打算找出哪些水晶球是有法力的，并用它们来统治世界。为达到这一邪恶企图，飞猪召集了一批地精工人来尝试水晶球的各种组合，一共 C_n+fⁿ 　种可能（即便这样，找到真正的水晶球也是遥遥无期……）。飞猪打算把这些任务分配给每个地精工人，而且每种组合只做一次试验。令她头疼的是，这些地精们还成立了一个工会，它们需要保证所有参加工作的地精的工作量是完全一样的。这样，就需要选择合适数量的地精来为飞猪大魔头工作，以保证这些工作能被平均地分配下去。
　　为了节省时间，飞猪需要召集尽可能多的地精。目前一共有 g (1 ≤ g ≤ 100000) 个地精愿意为她工作。大魔头飞猪重金聘请你来为她写个程序，要你计算出实际为她工作的地精数（小于等于 g），这个数必须能整除 C_n+fⁿ　，并且尽可能大。

　　第一行，一个整数 C (1≤ C ≤100)，表示一共有 C 组数据。
　　后面 C 行，每行三个整数 n, f, g 用空格分开。

　　C 行，每行对应输出最多能为大魔头工作的地精数。

4
3 1 3
3 3 50
4 3 4
15634 456 5000

2
20
1
4990