题目描述

一台打字机准备将1到10^n的数依次打出。在打印过程中，这台打字机出现了一个故障：数字“3”打不出来。因此，所有含有数字“3”的数都没有被正确地打出。试问没有被正确打出的数一共有多少个。

输入格式

输入一个正整数n。

输出格式

输出从1到10^n这些数中不能被正确打印的数的个数。

样例

input

2

output

19

限制与提示

保证$n\leq 1000$。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$