#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<queue>

#define Max 1000010
#define inf 0x3f3f3f3f


using namespace std;
int max(int x,int y) {if(x>y) return x;return y;}
int min(int x,int y) {if(x>y) return y;return x;}
int a[Max];   //a[i] 为当前构造的项
int b[Max];  //b[i]+1为下一项 
int main()
{
	int n,k,t,m,i,j,ans;
	scanf("%d",&m);
	for(int mm=1;mm<=m;mm++)
	{
		scanf("%d%d",&n,&k);
		a[0]=b[0]=1;
		i=j=0;//i是现在的位置，j是能否和p成k倍关系的数 
		while(n>a[i])
		{
			i++;
			a[i]=b[i-1]+1;
			while(a[j+1]*k<a[i])  //找到第一个k倍大于现在数的数 
			{
				j++;
			 }
			if(k*a[j]<a[i]) //如果存在k倍大于当前 
				b[i]=b[j]+a[i];
			else 
				b[i]=a[i];  //主要用来构造前面几项
			
		}
		if(n==a[i])
			ans=-1;
		else
		{
			while(n)//每个数都可以变成该数列的数相加,我们依次相减 
			{
				if(n>=a[i])
				{
					n-=a[i];
					ans=a[i];
				}
				i--;
			}
		}
		printf("Case %d: ",mm);
		if(ans==-1)
			printf("lose\n");
		else
			printf("%d\n",ans);
	}
	return 0;
}