#include <stdio.h>

int mdc(int primeiro, int segundo){ //pq esse int aqui e não no int main?
    int res, des; // qual a diferença desse pro de cima?
    if(primeiro ==0 && segundo ==0){
    return 0;
    }
    else if((primeiro ==1 && segundo ==0) || (segundo==1 && primeiro==0)){
        return 1;
    }
    if(primeiro>segundo){
        des=segundo;
        res=primeiro % des;
    }
    else{
        des=primeiro;
        res=segundo % des;
    }
    if(res==0){
        return des;
    }
    else{
        mdc(des, res);
    }
}
void variaveis(int valor, int inteiro){ //qual o sentido dessas variaveis? tipo qual a necessidade delas?
    int primeiro, segundo;
    if(inteiro <= valor){
        scanf("%d%d", &primeiro, &segundo);
    }
    else{
        return;
    }
    printf("MDC(%d,%d) = %d\n", primeiro, segundo, mdc(primeiro, segundo));
    variaveis(valor, inteiro+1);

}
int main() { // pq tem dois scanf agora?
    int valor;
    scanf("%d", &valor);
    variaveis(valor, 1);
    return 0;
}