Can anybody help me with the following problem, it was asked in one of the OAs of Uber:

You are given a cuboid with dimensions l, b and h. Your task is to make the volume equal to 0 in minimum possible steps. In each step you can reduce gcd(l,b,h) from either of l, b, or h.

that is if you start with dimension l,b,h and gcd(l,b,h) = g, then in one step you can reach to any one of the following dimensions:

1) l-g, b, h

2) l, b-g, h

3) l, b, h-g

Output the minimum number of steps required to reach a 0 volume cuboid. The limit on l,b,h is not mentioned in the problem statement.

I tried to solve this using 3D dp with l,b,h as states. But i got TLE on test-case: 9,24,35.

Is there any other possible solutions available?