Walter, Jesse and HCF

Problem Statement:

Walter and Jesse's friend Mike had helped them in making Crymeth and hence, they wanted to give him a share.
For deciding the share, they both decided to choose one number each, X and Y and found out that K^th Highest Common Factor of their two numbers is a good amount of Crymeth that can be given to Mike .
Walter and Jesse did this activity for D days in total. For each day, find out what quantity of Crymeth they decided to give to Mike.

Input:

First line contains a natural number D - the total number of days.
D lines follow. Each line contains three natural numbers - X, Y and K.

Output:

For each day, print the quantity given to Mike on a new line.
If the K^th HCF of X and Y does not exist, simply print "No crymeth today" (Without the quotes)

Constraints:

• 1 ≤ D ≤ 10³
• 1 ≤ X, Y, K ≤ 10¹⁰

Code

import java.util.*;

class TestClass {

   public static void main(String args[] ) throws Exception {

       Scanner sc=new Scanner(System.in);

       int d=sc.nextInt();

       for(int q=0;q<d;q++)

       {

           long x=sc.nextLong();

           long y=sc.nextLong();

           int k=sc.nextInt();

//GCD CALCULATION

           long a=x>y?x:y;

           long b=x<y?x:y;

           long r=b;

           while(a%b!=0)

           {

               r=a%b;

               a=b;

               b=r;

           }

           long gcd=r;

           

// CALCULATING ALL FACTORS OF GCD

           ArrayList<Long> left= new ArrayList<Long>();

           ArrayList<Long> right= new ArrayList<Long>();

           long u=1;

           while(u<=(Math.sqrt(gcd)+1))

           {

               if(gcd%u==0){

                   if(!left.contains(u) && !right.contains(u)){

                   left.add(u);}

                   if(!left.contains(gcd/u) && !right.contains(gcd/u))

                   {

                   right.add(gcd/u);}

               }

               u++;

           }

           

           ArrayList <Long>all=new ArrayList<Long>();

           Collections.reverse(left);

           all.addAll(right);

           all.addAll(left);

 

           if(all.size()<k)

           {

               System.out.println("No crymeth today");

           }

           else

           {

           long kth=all.get(k-1);

           System.out.println(kth);

           }

       }

       }

   }

}