#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <string>

#include <stack>

#include <vector>

#include <map>

#include <queue>

#include <algorithm>

#include <utility>

using namespace std;

typedef long long LL;

const int N=1e4+;

const int INF=0x3f3f3f3f;

const LL mod=1e9+;

bool vis[N];

int cur[N*];

int main()

{

    int T,cas=;

    scanf("%d",&T);

    while(T--){

      LL x,m,k,c;

      scanf("%I64d%I64d%I64d%I64d",&x,&m,&k,&c);

      LL t=,cnt=;

      bool flag=;

      memset(vis,,sizeof(vis));

      for(;;++cnt){

        t=t*+x;

        if(vis[t%k]){flag=;break;}

        vis[t%k]=;cur[cnt]=t%k;

        t%=k;

      }

      if(flag){m%=cnt;if(m==)m=cnt;}

      printf("Case #%d:\n",++cas);

      if(cur[m]==c)printf("Yes\n");

      else printf("No\n");

    }

    return ;

}