#include<iostream>#include<cstdio>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<cmath>#include<vector>#include<algorithm>#define inf 1000000000#define eps 1e-8typedef long long LL;using namespace std;LL l,r,c,k;int p=50;LL dp[50][200][2];int wei[40];int cw[40];LL dfs(int cnt,int cha,int flag,int type){ if(dp[cnt][cha+p][flag]!=-1) return dp[cnt][cha+p][flag]; dp[cnt][cha+p][flag]=0; if(cnt==32) { if(cha==0&&flag) { dp[cnt][cha+p][flag]=1; } return dp[cnt][cha+p][flag]; } if(type==1) { if(cw[cnt]==0) { if(wei[cnt]==1) dp[cnt][cha+p][flag]+=dfs(cnt+1,cha-1,1,type); else dp[cnt][cha+p][flag]+=dfs(cnt+1,cha-1,flag,type); } else { if(wei[cnt]==1) dp[cnt][cha+p][flag]+=dfs(cnt+1,cha-1,1,type); else dp[cnt][cha+p][flag]+=dfs(cnt+1,cha-1,flag,type); if(wei[cnt]==0) dp[cnt][cha+p][flag]+=dfs(cnt+1,cha+1,0,type); else dp[cnt][cha+p][flag]+=dfs(cnt+1,cha+1,flag,type); } } else if(type==2) { if(cw[cnt]==0) { if(wei[cnt]==1) dp[cnt][cha+p][flag]+=dfs(cnt+1,cha-1,1,type); else dp[cnt][cha+p][flag]+=dfs(cnt+1,cha-1,flag,type); if(wei[cnt]==0) dp[cnt][cha+p][flag]+=dfs(cnt+1,cha+1,0,type); else dp[cnt][cha+p][flag]+=dfs(cnt+1,cha+1,flag,type); } } else { if(cw[cnt]==0) { if(wei[cnt]==1) dp[cnt][cha+p][flag]+=dfs(cnt+1,cha-1,1,type); else dp[cnt][cha+p][flag]+=dfs(cnt+1,cha-1,flag,type); if(wei[cnt]==0) dp[cnt][cha+p][flag]+=dfs(cnt+1,cha+1,0,type); else dp[cnt][cha+p][flag]+=dfs(cnt+1,cha+1,flag,type); } else { if(wei[cnt]==0) dp[cnt][cha+p][flag]+=dfs(cnt+1,cha+1,0,type); else dp[cnt][cha+p][flag]+=dfs(cnt+1,cha+1,flag,type); } } return dp[cnt][cha+p][flag];}LL solve(int type,LL w){ if(w<0) return 0; int ix=0; memset(wei,0,sizeof(wei)); while(w) { wei[ix++]=w%2; w/=2; } memset(dp,-1,sizeof(dp)); LL ans=0; for(int i=-k;i<=k;i++) { ans+=dfs(0,i,1,type); } return ans;}int main(){ int t; scanf("%d",&t); int cas=1; while(t--) { scanf("%lld%lld%lld%lld",&l,&r,&c,&k); int ix=0; memset(cw,0,sizeof(cw)); while(c) { cw[ix++]=c%2; c/=2; } printf("Case %d: ",cas++); printf("%lld %lld %lldn",solve(1,r)-solve(1,l-1),solve(2,r)-solve(2,l-1),solve(3,r)-solve(3,l-1)); } return 0;}
