App:  Use Inclusion - Exclusion 

Entree:  Write binom(n,k)^2 as binom(n,k) * binom(n,n-k) and think about the first hint.

Dessert:  By inclusion exclusion you should be able to find that the diagonal passes through the interiors of 

w+l+h - gcd(w,l)-gcd(w,h)-gcd(l,h)+gcd(l,w,h)

cubes.