New Product

题目背景

**一个经商的神奇故事……** (善意提醒:注意时限!)

题目描述

LiM有一家手工糕点店,因为糕点既实惠又好吃,于是积累了$P$个常客。($P$为质数) 每次这家店出$New Product$(新品)的时候,都会做很多个,这$P$个人都会支持,支持方法是: **每个人买的数量都相同,而且买的总数要尽量多** 这家店共有$B$个工人,一分钟可以生产已经生产的数量的$A$倍。 (注:一开始有一个已制作的$New Product$作为制作样品) 而当制作完毕,抢购(只考虑常客)完后: **为了考虑工人们,最后要剩下正好$B$个。** 下面给出已知条件,请你帮LiM算算最少要工作多长时间吧!

输入输出格式

输入格式


共$T+1$行。 第一行一个数$T$,表示共要出$T$个$New Product$。 第$2$~$T+1$行,每行三个数,$P$,$A$,$B$,意义如题。

输出格式


对于每个$New Product$: 如果可以实现(有可能不行),输出最少工作的分钟数。 如果不行,输出"Couldn't Produce!"

输入输出样例

输入样例 #1

1
5 2 3

输出样例 #1

3

输入样例 #2

1
2 2 2

输出样例 #2

Couldn't Produce!

说明

样例1解释: 有5个常客,一分钟可以生产已生产的2倍,有3个工人。 则最小需要三分钟(生产$2^3=8$个)才能符合要求。 样例2解释: 有2个常客,一分钟可以生产已生产的2倍,有2个工人。 因为不管是多长时间都会余下0个,所以输出“Couldn't Produce!” ---------------------------------------------- 说明: LiM不是工人哦! 对于每组$New Product$,常客数量不同。 对于$20$%的数据,$T=1$,所有条件$<=100$。 对于$100$%的数据,$T<=5000$,所有条件$<=50000$。$P$为质数!