You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

Input Format

输入一个正整数n。

Output Format

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

Sample

input

2

output

19

Hint

保证$n\leq 1000$。

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

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