Faktor persekutuan terbesar

Diberikan dua bilangan bulat positif A dan B. Anda diminta untuk menemukan GCD (Greatest Common Divisor) atau yang biasa disebut FPB dari kedua bilangan tersebut menggunakan pendekatan rekursif.

Format Masukan

Baris pertama berisi sebuah bilangan bulat T, menyatakan jumlah kasus uji. Kemudian, untuk setiap kasus uji, terdapat satu baris berisi dua bilangan bulat A dan B, dipisahkan oleh spasi.

Format Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi hasil GCD dari A dan B.

Contoh Masukan 1

2
48 18
81 27

Contoh Keluaran 1

6
27

Penjelasan:

• Pada kasus uji pertama, faktor-faktor dari 48 adalah: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. Faktor-faktor dari 18 adalah: 1, 2, 3, 6, 9, 18. Maka, GCD dari 48 dan 18 adalah 6.

• Pada kasus uji kedua, faktor-faktor dari 81 adalah: 1, 3, 9, 27, 81. Faktor-faktor dari 27 adalah: 1, 3, 9, 27. Maka, GCD dari 81 dan 27 adalah 27.