import java.io.*;import java.util.*;class Main{ public static int gcd(int m,int n) {while (true) {if ((m = m % n) == 0) return n;if ((n = n % m) == 0) return m;} } public static void main(Stri...