Превышен лимит времени в упражнении hackerearth

Я пытаюсь решить это упражнение в HackerEarth. Но у меня ошибка срок превышен. Это код, который я написал:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TestClass {
    //gcd 
    public static long gcd(long num1, long num2) {
        if (num2 != 0) {
            return gcd(num2, num1 % num2);
        } else {
            return num1;
        }
    }

    public static void main(String args[] ) throws Exception {
        //BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // Reading input from STDIN
        while (T-- > 0) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st1.nextToken());
            long b = Long.parseLong(st1.nextToken());
            long A = a/gcd(a,b);
            long B = b/gcd(a,b);
            System.out.printf("%d%1s%d%n",B,"",A);
        }
    }
}