Description

X星人特别的喜欢追求完美，他们觉得阶乘是最完美的，因为涉及到小于等于n的全部自然数。而且他门读数字是从右往左的， 并且在他们的字典里没有数字0。他们把N！的第一个数字称为N的X数(按他们的读数字的规则）。比如5的X数是2，4的X数是4， 6的X数是2。现在请你帮他们求一些数的X数。

Input

有多行输入，每行一个数N(0=<N<=10^101)

Output

每行输出N的X数。

Sample

Input

1
5
4
6

Output

1
2
4
2