问题描述

在你的帮助下， 达克终于打开了石门， 进去后发现里面有个面目狰狞的妖怪。 这只妖怪正怒视着轩轩， 然后一言不发的在地上写了一串数字： 1，12， 123， 1234， 12345， … … ， 12345678910， 1234567891011， … … 。 然后告诉达克： “ 你要是能知道这个数列的前 n 项里有多少项能被 3 整除， 我就放你过去， 否则， 嘿嘿… … 吃了你！ ” 。

看来这个妖怪的数学不错。 不过数学更是达克的强项， 很快就算出了答案。 你知道怎么算吗?

输入格式

一个整数$n$

输出格式

一个整数， 表示这个数列的前 $n$ 项里有多少项能被 3 整除

样例

5

3

数据范围

• 对于 30%的数据， 满足 $n \leq10$
• 对于 100%的数据， 满足 $n \leq 2^{31}-1$

来源

2021 NOIP 山东(小学组)