Need explicit formula for certain "$q$-numbers" involving gcd's

Question

The question is motivated by yet another possible approach to a combinatorial problem formulated previously in "Special" meanders. I'm not giving details of the connection as I believe the question is sufficiently motivated by itself.

I've got a vector space with basis $\left\{e_n\mid n\geqslant0\right\}$ and scalar product $$ \left\langle e_m,e_n\right\rangle=q^{\gcd(m,n)} $$ (with the convention $\gcd(0,n)=n$ for all $n\geqslant0$).

What I need is a maximally explicit expression for an orthogonal basis $\left\{o_n\mid n\geqslant0\right\}$ with respect to this scalar product. I do not mind if the $o_n$ are not of unit norm (and this is clearly a minor point anyway).

Here are the first few values (calculated with MAPLE). Up to arbitrary rescalings, \begin{align*} o_{{0}}&=e_{{0}}\\ o_{{1}}&=e_{{1}}-qe_{{0}}\\ o_{{2}}&=e_{{2}}- \left( q+1 \right) e_{{1}}+qe_{{0}}\\ o_{{3}}&=e_{{3}}-qe_{{2}}-e_{{1}}+qe_{{0}}\\ o_{{4}}&=\left( q+1 \right) e_{{4}}-{q}^{2}e_{{3}}- \left( {q}^{2}+q+1 \right) e_{{2}}+{q}^{2}e_{{1}}+{q}^{2}e_{{0}}\\ o_{{5}}&=\left( {q}^{2}+q+1 \right) e_{{5}}- \left( {q}^{2}+1 \right) qe_{{4}}- \left( {q}^{2}+1 \right) qe_{{3}}+ \left( {q}^{3}-{q}^{2}-1 \right) e_{{1}}+ \left( {q}^{2}+1 \right) qe_{{0}}\\ o_{{6}}&=\left( {q}^{3}+{q}^{2}+2\,q+1 \right) e_{{6}}- \left( {q}^{3} +q-1 \right) qe_{{5}}- \left( {q}^{3}+q-1 \right) qe_{{4}}\\&- \left( {q} ^{2}+1 \right) \left( {q}^{2}+q+1 \right) e_{{3}}- \left( {q}^{3}+{q} ^{2}+2\,q+1 \right) e_{{2}}+ \left( 2\,{q}^{4}+{q}^{3}+3\,{q}^{2}+1 \right) e_{{1}}+ \left( {q}^{3}+q-1 \right) qe_{{0}}\\ o_{{7}}&=\left( {q}^{2}+1 \right) e_{{7}}- \left( {q}^{2}-q+1 \right) qe_{{6}}- \left( {q}^{2}-q+1 \right) qe_{{5}}- \left( {q}^{2}-q+1 \right) qe_{{4}}\\&+ \left( {q}^{2}-q+1 \right) qe_{{2}}+ \left( {q}^{3} -2\,{q}^{2}+q-1 \right) e_{{1}}+ \left( {q}^{2}-q+1 \right) qe_{{0}} \end{align*}

The inverse transformation (again up to rescalings) does not look any more enlightening (except that everything is positive):

\begin{align*} e_{{0}}&=o_{{0}}\\ e_{{1}}&=o_{{1}}+qo_{{0}}\\ e_{{2}}&=o_{{2}}+ \left( q+1 \right) o_{{1}}+{q}^{2}o_{{0}}\\ e_{{3}}&=o_{{3}}+qo_{{2}}+ \left( {q}^{2}+q+1 \right) o_{{1}}+{q}^{3}o_ {{0}}\\ e_{{4}}&=o_{{4}}+{\frac {{q}^{2}}{q+1}}o_{{3}}+ \left( {q}^{2}+1 \right) o_{{2}}+ \left( q+1 \right) \left( {q}^{2}+1 \right) o_{{1}} +{q}^{4}o_{{0}}\\ e_{{5}}&=o_{{5}}+{\frac { \left( {q}^{2}+1 \right) q}{{q}^{2}+q+ 1}}o_{{4}}+{\frac {q \left( {q}^{2}+1 \right)}{q+1}} o_{{3}}+q \left( {q}^{2} +1 \right) o_{{2}}+ \left( {q}^{4}+{q}^{3}+{q}^{2}+q+1 \right) o_{{1}} +{q}^{5}o_{{0}}\\ e_{{6}}&=o_{{6}}+{\frac { \left( {q}^{3}+q-1 \right) q}{{q}^{3}+ {q}^{2}+2\,q+1}}o_{{5}}+{\frac { \left( {q}^{3}+q-1 \right) q}{{q}^{2} +q+1}}o_{{4}}+{\frac { \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right)}{q+1}} o_{{3}}\\ &+ \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+ 1 \right) o_{{2}}+ \left( q+1 \right) \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right) o_{{1}}+{q}^{6}o_{{0}}\\ e_{{7}}&=o_{{7}}+{\frac { \left( {q}^{2}-q+1 \right) q}{{q}^{2}+ 1}}o_{{6}}+{\frac { \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right) q}{{q}^{3}+{q}^{2}+2\,q+1}}o_{{5}}+ \left( {q}^{2}-q+1 \right) qo_{{4}}\\ &+{\frac {q \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right)}{q+1}}o_{{3}} +q \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right) o_{{2}} + \left( {q}^{6}+{q}^{5}+{q}^{4}+{q}^{3}+{q}^{2}+q+1 \right) o_{{1}}+{q}^{7}o_{{0}}\\ e_{{8}}&=o_{{8}}+{\frac { \left( {q}^{2}+1 \right) {q}^{4}}{ \left( {q}^{2}+q+1 \right) \left( {q}^{3}+q+1 \right) }}o_{{7}}+{\frac {{q} ^{4}}{{q}^{2}+q+1}}o_{{6}}+{\frac { \left( {q}^{2}+1 \right) {q}^{4}}{{q}^{3}+{q}^{2}+2\,q+1}}o_{{5}}\\ &+{\frac { {q}^{6}+{q}^{4}+{q}^{2}+q+1 }{{q}^{2}+q+1}}o_{{4}} +{\frac {{q}^{2} \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right)}{q+1}}o_{{3}}+ \left( {q}^{2}+1\right) \left( {q}^{4}+1 \right) o_{{2}}+ \left( q+1 \right) \left( {q}^{2}+1 \right) \left( {q}^{4}+1 \right) o_{{1}}+{q}^{8}o_{ {0}} \end{align*}

There are some patterns, but I cannot even guess any statement that I could try to prove about these coefficients. Also the above was computed under the assumption that the transformation matrix is triangular, i. e. that $o_n$ only depends on $e_k$ with $k\leqslant n$. It is quite possible that there is a nicer basis which violates this assumption, but again I cannot think of any natural alternative form of the transformation matrix.

What I know is an explicit orthogonal basis for a similar scalar product "without $q$": if I would have just $\left\langle e_m,e_n\right\rangle=\gcd(m,n)$, then an orthogonal basis would be given by $e_n=\sum_{d|n}o_d$, so $o_n=\sum_{d|n}\mu\left(\frac nd\right)e_d$. Strangely enough, I obtain this from the above by substituting $q=0$, and again I have no idea why.

As @alpoge points out in a comment, if one removes $e_0$, then this actually works "with $q$" too.

PS As suggested by @Wolfgang in a comment, I've looked at polynomials resulting from the substitutions $q=\pm1$, $e_n=x^n$. Here:

$q=1$: \begin{align*} &1\\ &x-1\\ & \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 2\,x+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 3\,{x}^{2}+x+2 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 5\,{x}^{3}+4\,{x}^{2}+8\,x+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( {x}^{2}+x+1 \right) \left( 2\,{x}^{2}-x+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 9\,{x}^{5}+7\,{x}^{4}+14\,{x}^{3}+10\,{x}^ {2}+6\,x+2 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 11\,{x}^{6}+8\,{x}^{5}+16\,{x}^{4}+10\,{x} ^{3}+15\,{x}^{2}+9\,x+3 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 7\,{x}^{5}+6\,{x}^{4}+5\,{x}^{3}+4\,{x}^{2 }+10\,x+1 \right) \left( {x}^{2}+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 16\,{x}^{8}+11\,{x}^{7}+22\,{x}^{6}+12\,{x }^{5}+18\,{x}^{4}+3\,{x}^{3}+9\,{x}^{2}-6\,x+5 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 21\,{x}^{9}+19\,{x}^{8}+38\,{x}^{7}+34\,{x }^{6}+51\,{x}^{5}+45\,{x}^{4}+39\,{x}^{3}+33\,{x}^{2}+6\,x+2 \right) \left( x-1 \right) ^{2} \end{align*} $q=-1$: \begin{align*} 0&:1\\ 1&:1+x\\ 2&:\left( x-1 \right) \left( 1+x \right)\\ 3&:\left( x-1 \right) \left( 1+x \right) ^{2}\\ 4&:- \left( x-1 \right) \left( 1+x \right) ^{2}\\ 5&:\left( x-1 \right) \left( {x}^{2}+x+2 \right) \left( 1+x\right) ^{2}\\ 6&:-\left( x-1 \right) \left( {x}^{3}+2\,{x}^{2}+2\,x+3 \right) \left( 1+x \right) ^{2}\\ 7&:\left( x-1 \right) \left( {x}^{2}+x+1 \right) \left( 2\,{x}^{2}- x+3 \right) \left( 1+x \right) ^{2}\\ 8&:-\left( x-1 \right) \left( {x}^{4}+2\,{x}^{2}+2 \right) \left( 1 +x \right) ^{3}\\ 9&:\left( x-1 \right) \left( {x}^{5}+{x}^{4}+{x}^{3}+3\,{x}^{2}+3 \right) \left( 1+x \right) ^{3}\\ 10&:- \left( x-1 \right) \left( {x}^{2}+1 \right) \left( {x}^{5}+2\, {x}^{4}+{x}^{3}+2\,{x}^{2}+2\,x+3 \right) \left( 1+x \right) ^{2}\\ 11&:\left( x-1 \right) \left( 4\,{x}^{8}+{x}^{7}+8\,{x}^{6}+2\,{x}^{ 5}+12\,{x}^{4}+3\,{x}^{3}+11\,{x}^{2}+4\,x+5 \right) \left( 1+x \right) ^{2} \end{align*}