菜鸟是个奇怪的人，他整天喜欢琢磨一些东西... 某天，他在想：如果一个数k加上n次a而且乘上m次b，然后再对p取余，之后这个数最大会变成多少呢?? 因为今天菜鸟在忙于期末考试，所以现在请你来帮助解决一下这个问题(对这个数每次你可以选择加a或者乘b 但是你总的必须要用n次加法和m次乘法)。

多组测试数据，第一行有一个整数t(1<=t<=20)代表case数量对于每个case有六个整数knmabp分别代表这个数n次加法m次乘法每次加上a每次乘上b，最后对p取余(1<=knmabp<=100)。

每个case形如"Case #K: M"K代表case数从1开始M代表对k这个数在进行上面操作后对p取余的最大数。