Java implementation of the approach
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int __gcd ( int a , int b ) { if ( b == 0 ) return a ; return __gcd ( b , a % b ) ; }