$d(A)$-ээр $n$ тооны цифрүүдийн нийлбэрийг олж, гарсан тооны цифрүүдийн нийлбэрийг мөн олох замаар 1 оронтой болтол үргэлжлүүлж гарсан тоог тэмдэглэе.

Жишээ нь: $d(6543) = d(6 + 5 + 4 + 3) = d(18) = 9$.

$1 ≤ A, B, C ≤ N$ ба $A × B ≠ C$ боловч $d(A × B) = d(C)$ байдаг бүх $A$, $B$, $C$ хосын тоог олно уу.

Оролт

$N$ тоо $(1 ≤ N ≤ 1000000)$.

Гаралт

Хариу болох ганц тоо.

For the first sample the required triples are $(3, 4, 3)$ and $(4, 3, 3)$.