m@main=getLine>>=putStrLn.f.lex>>m
f[(a,s:b)]=a#b:[s:b#a|b#a>"1"]>>=id
a#b=show$div%a$gcd%a%b
(%)=(.read)