#include <cstdio>
#include <set>

using namespace std;

typedef long long ll;

ll x, MOD;

struct Matrix2{
	ll a[2][2];

	bool operator<(const Matrix2 &r)const{
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				if (a[i][j] != r.a[i][j])
					return a[i][j] < r.a[i][j];
		return false;
	}
};

Matrix2 operator*(const Matrix2 &l, const Matrix2 &r){
	Matrix2 ret;
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			ret.a[i][j] = (l.a[i][0] * r.a[0][j] + l.a[i][1] * r.a[1][j]) % MOD;
	return ret;
}

ll expMod(ll e, ll n, ll p){
	ll ret = 1;
	for (; n; n >>= 1){
		if (n & 1)
			ret = ret * e % p;
		e = e * e % p;
	}
	return ret;
}

void expMod(Matrix2 &ret, Matrix2 e, ll n){
	for (; n; n >>= 1){
		if (n & 1)
			ret = e * ret;
		e = e * e;
	}
}

int main(){
	int cas;
	scanf("%d", &cas);
	for (int casi = 1; casi <= cas; ++casi){
		scanf("%lld%lld", &x, &MOD);
		ll length = (MOD - 1) * (MOD + 1);
		ll y = (1 + expMod(2, x, length)) % length;
		Matrix2 S = {2 % MOD, 0, 10 % MOD, 0}, A = {10, MOD - 1, 1, 0};
		expMod(S, A, y);
		printf("Case #%d: %d\n", casi, (int)((S.a[0][0]) - 1 + MOD) % MOD);
	}
	return 0;
}