RSA HNumber

#include "stdio.h"

/*
Author: Arthur Henrique
Creation: 20/12/2013
email: arthur393 (at) gmail(dot) com
*/

int mdc(int x, int y){ //Função Iterativa mais rapida que você correndo do capiroto
    int a, b, temp;
    a = x;
    b = y;
    while (y != 0) {
        temp = x;
        x = y;
        y = temp%y;
    }
    return x;
}

int main(){
    int i,k,qtd,q,n=0,m=0;
    scanf("%d",&q);
    for(i=0;i<q && q<1000000;i++){          // Q( 1 <= Q <= 10^5)
        qtd=0;
        scanf("%d",&n);
        scanf("%d",&m);
        if((n>0) && (m<1000000) && (m<=n)){ // N e M( 1 <= N, M <= 10^5, M < N)
            for(k=1;k<=m;k++){
                if (mdc(n,k)==1){   //SE O RESULTADO DE UM MMC ENTRE X E Y,
                qtd++;              //FOR IGUAL AO PRODUTO DE X E Y. OU SEJA,
                                    //printf("%d, ",x);
                }                   //MMC(X,Y)== X*Y, ENTÃO O
            }                       //MDC ENTRE X E Y É 1
            printf("%d\n",qtd);
        }
    }
}