Last Digit

The number of permutation without repetition that has a string S is so big, but in this problem you just need to print the last nonzero digit of it.

Input

In each test case you have a string S (1 <= |S| <= 1000000), all characters in the string are lowercase.

Output

For each test case print the last nonzero digit.

Sample Input

aaba
aaabababababa
abbzazzazzalzalzzaaaaazlalzaazlalzla
w
Sample Output

4
7
8
1
Hints

For example for the first test case the permutation are:
aaab
aaba
abaa
baaa