object Main{
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a
    else gcd(b, a % b)
 
  def simplifyFrac(a: Int, b: Int) = {
    (a / gcd(a, b), b / gcd(a, b))
  }
 
  //print
  def main(args: Array[String]): Unit = {
    println(simplifyFrac(4, 8))
    println(simplifyFrac(1536, 78360))
    println(simplifyFrac(51478, 5536))
    println(simplifyFrac(46410, 119340))
    println(simplifyFrac(7673, 4729))
    println(simplifyFrac(4096, 1024))
  }
 
}

b2JqZWN0IE1haW57CiAgZGVmIGdjZChhOiBJbnQsIGI6IEludCk6IEludCA9CiAgICBpZiAoYiA9PSAwKSBhCiAgICBlbHNlIGdjZChiLCBhICUgYikKCiAgZGVmIHNpbXBsaWZ5RnJhYyhhOiBJbnQsIGI6IEludCkgPSB7CiAgICAoYSAvIGdjZChhLCBiKSwgYiAvIGdjZChhLCBiKSkKICB9CgogIC8vcHJpbnQKICBkZWYgbWFpbihhcmdzOiBBcnJheVtTdHJpbmddKTogVW5pdCA9IHsKICAgIHByaW50bG4oc2ltcGxpZnlGcmFjKDQsIDgpKQogICAgcHJpbnRsbihzaW1wbGlmeUZyYWMoMTUzNiwgNzgzNjApKQogICAgcHJpbnRsbihzaW1wbGlmeUZyYWMoNTE0NzgsIDU1MzYpKQogICAgcHJpbnRsbihzaW1wbGlmeUZyYWMoNDY0MTAsIDExOTM0MCkpCiAgICBwcmludGxuKHNpbXBsaWZ5RnJhYyg3NjczLCA0NzI5KSkKICAgIHByaW50bG4oc2ltcGxpZnlGcmFjKDQwOTYsIDEwMjQpKQogIH0KCn0=