893 : マッチ棒

$M(n)$ を、数 $n$ を表現するのに必要な最小のマッチ棒の本数と定義する。

数は桁の数字として表すことと、加算および乗算を含む式として表すことができる。また、演算の順序は規則に従い、乗算は加算よりも優先される。その他の記号や演算、例えば括弧、減算、除算、べき乗は使用できない。

使用可能な数字と記号は以下の通り：

例えば、28 は数字として表すとマッチ棒が12本必要だが、$4 \times 7$ と表現すればマッチ棒は9本で済む。これより少ないマッチ棒で表現する方法はないため、$M(28) = 9$ となる。

$\displaystyle T(N) = \sum_{n=1}^N M(n)$ と定義する。$T(100) = 916$ が与えられている。

$T(10^6)$ を求めよ。