D. Chatbot on a Calculator
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Did you know that in the past, even calculators were programmed in computer science classes?

The author of this problem personally learned about this from their parents, who did something similar in the late 1980s.

In 2026, the main trend is communicating with various LLM models in chat mode (and not only that).

But is it possible to communicate in a similar way with a chatbot programmed on a calculator?

It is possible if we consider some digits to be similar to letters of the Latin alphabet:

  • digit 0 is similar to O;
  • digit 1 is similar to I;
  • digit 5 is similar to S;
  • digit 8 is similar to B.

And if you turn the calculator upside down, you can see two more correspondences:

  • digit 3 is similar to an upside-down E;
  • digit 7 is similar to an upside-down L.

We will call a number $$$X$$$ a "word" if all of its digits are similar to letters:

  • number 8015 looks like the word "BOIS";
  • number 5337 does not look like a word, but when turned upside down it looks like "LEES";
  • number 123 does not look like a word, since digit 2 is not similar to any letter;
  • number 0158 is not a valid number, since it starts with a leading zero.

Your task is to determine the number of word-like numbers in the interval $$$[0; N]$$$.

Input

The only line contains one integer $$$N$$$ $$$(0 \le N \le 123456)$$$ — the upper bound of the interval $$$[0; N]$$$.

Output

Print two integers $$$C_1$$$ and $$$C_2$$$ separated by a space:

  • $$$C_1$$$ — the number of numbers in the interval $$$[0; N]$$$ that look like a word in the normal orientation;
  • $$$C_2$$$ — the number of numbers in the interval $$$[0; N]$$$ that look like a word in the turned upside down orientation.
Examples
Input
34
Output
8 15
Input
8051
Output
202 1100
Input
123456
Output
1536 10368
Note

Example 1.

In the normal orientation, the following numbers look like words:

  • $$$0, 1, 5, 8$$$;
  • $$$10, 11, 15, 18$$$.
There are $$$8$$$ such numbers in the interval $$$[0; 34]$$$.

In the turned upside down orientation, the following numbers look like words:

  • $$$0, 1, 3, 5, 7, 8$$$;
  • $$$10, 11, 13, 15, 17, 18$$$;
  • $$$30, 31, 33$$$.
There are $$$15$$$ such numbers in the interval $$$[0; 34]$$$.

Example 2.

This test is an additional opportunity to check that your counting is performed correctly.

Example 3.

This test checks that your counting is performed efficiently enough (the bound $$$N$$$ takes its maximum possible value).