#include <stdio.h>

int main(){
    bool flag[100001];
    int cycle[100001];
    long long n,a,b,index,count;
    int tc;
    scanf("%d",&tc);
    for(int i=1;i<=tc;i++){
        count = 0, index = 0;
        scanf("%lld %lld %lld",&n,&a,&b);
        while(1){
            if(flag[a]){
                for(int j=0;j<count;j++){
                    if(cycle[j]==a){
                        printf("Case #%d: %lld\n",i,count-j);
                        break;
                    }
                }
                break;
            }
            flag[a] = true;
            cycle[index++] = a;
            a = (a*b)%n;
            count++;
        }
        for(int j=0;j<=count;j++){
            flag[cycle[j]] = false;
            cycle[j] = 0;
        }
    }
    return 0;
}