for(m=(r=readline)(print(n=r(f=r())));m--;)for(x=1,r=/\d+/g;a=r(f)*n;x=a%b<x?print(n=a/b):x)b=r(f)