Problemi 111

Kërkesa

Një drejtkëndësh me përmasa A dhe B duam ta ndajmë në copa katrore (jo detyrimisht të barabarta). Sa është numri më i vogël i katrorëve në të cilët mund të ndahet ky drejtkëndësh?

Shembull

$ cat input.txt
2
10 15
4 7

$ python3 prog.py < input.txt
3
5

Zgjidhja

for _ in range(int(input())):
    a, b = map(int, input().split())
    nr = 0
    while b > 0:
        nr += a // b
        a, b = b, a % b
    print(nr)