int nwd(int a, int b)
{
    if(a * b == 0)
        return 1;
    if(a < 0)
        a = -a;
    if(b < 0)
        b = -b;
    while(a != b)
    {
        if(a > b)
            a -= b;
        if(b > a)
            b -= a;
    }
    return a;
}