1. 

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: number theory
* Problem: 11774-DoomsDay
* Accepted: 0.048
* @author Evgeni Pavlidis
*
*/

#include <iostream>

using namespace std;

unsigned long long gcd(unsigned long long a, unsigned long long b)
{
return (b == 0)? a : gcd(b, a % b);
}

int main()
{
int testCases;
cin >> testCases;
unsigned long long n, m, tmp, t;
unsigned long mod;


for(int tc = 1; tc <= testCases; tc++)
{
cin >> n;
cin >> m;
mod = n*m;

int ggT = gcd (m,n);
m /= ggT;
n /= ggT;
cout << "Case " << tc << ": " << m + n << "\n";
}
return 0;
}