Przekroczenie czasu w zadaniu NWD

#include <iostream>

using namespace std;

//funkcja obliczająca nwd
int nwd( int a, int b )
{
    int r, i, n;
   
    if( a <= b ) n = a;
    else n = b;
   
    for( i = 1; i <= n; i++ )
    {
        if( a % i == 0 && b % i == 0 )
             r = i;
       
    }
    return r;
}

int main()
{
    int t, k;
    //t to licba wywołań funkcji nwd(a,b)
    cin >> t;
    for( k = 1; k <= t; k++ )
    {
        int a, b;
        cin >> a >> b;
        cout << nwd( a, b ) << endl;
    }