def euclide(a,b): while b!=0: a,b = b,a%b return a