import java.io.* ;

import java.math.* ;

import java.util.* ;

import java.text.* ;

public class Main

{

    public static void main(String[] args)

    {

        Scanner cin=new Scanner (new BufferedInputStream(System.in)) ;

        BigInteger A,B ;

        int t=cin.nextInt() ;

        for (int cas= ;cas<=t ;cas++)

        {

            A=cin.nextBigInteger() ;

            B=cin.nextBigInteger() ;

            System.out.print("Case #"+cas+": ") ;

            System.out.println(A.gcd(B).toString()) ;

        }

    }

}