2130 - ラッキーナンバーの個数が知りたいKsansansan君

問題

Ksansansan君は$N$以下のラッキーナンバーの個数を知りたがっています。
ある整数 $N$ が与えられた時、$N$以下の自然数のうち、ラッキーナンバーである個数を求めて下さい。

ラッキーナンバーの定義

以下の条件のいずれかを満たす整数 $X$ を、ラッキーナンバーとします。

• $X$のいずれかの桁が3である。
• $X$が3の倍数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

整数 $N$ が与えられる。

出力

$N$以下の自然数のうち、ラッキーナンバーの個数を出力すること。また、出力の最後に改行を入れること。
出力が32bitに収まらないことがあるので気を付けること。

制約

全ての入出力ケースについて以下を満たす。

• $N \leq 10^{18}$
• 入力は自然数である。

入出力例

入力例1

20

出力例1

7

$3$,$6$,$9$,$12$,$13$,$15$,$18$の7つが条件を満たします。

入力例2

2

出力例2

0

条件を満たす数は1つも存在しません。

入力例3

998244353

出力例3

740579141