波利卡普的商店里有n把铲子。第 i 铲子花费 i 节,即第一把铲子花费 1 节,第二把铲子花费 2 节,第三把铲子花费 3 节,以此类推。波利卡普斯想要成对出售铲子。
如果总成本以几个 9 结尾,访客更有可能购买一把铲子。因此,波利卡普想要选择一对铲子来出售,使得它们的成本总和以最大可能的 9 个数结尾。例如,如果他选择成本为 12345 和 37454 的铲子,则它们的总成本为 49799,以两个 9 结尾。
您要计算铲子对的数量,使得它们的总成本以最大可能的 9 个数结束。如果一对中有铲子,而另一对中没有,则认为两对不同。
输入
第一行包含一个整数 n (2 ≤ n ≤ 109) — 波利卡普商店中的铲子数量。
输出
打印铲子对的数量,使其总成本以最大可能数量的 9 结尾。
注意,最后的9的最大个数有可能是0,那么你应该把这样的方式都数一遍。
保证对于每个 n ≤ 109,答案不超过 2·109。
示例
输入 #1
7
输出 #1
3
输入 #2
14
输出 #2
9
输入 #3
50
输出 #3
1
注意
在第一个示例中,末尾的 9 的最大可能数量是 1。 Polycarp 为此目的选择以下几对铲子:
- 2 和 7;
- 3 和 6;
- 4 和 5。
在第二个示例中,两把铲子的总成本末尾的 9 的最大数量是 1。以下几对铲子适合波利卡普:
- 1 和 8;
- 2 和 7;
- 3 和 6;
- 4 和 5;
- 5 和 14;
- 6 和 13;
- 7 和 12;
- 8 和 11;
- 9 和 10。
在第三个示例中,需要选择铲子 49 和 50,因为它们的成本之和为 99,这意味着 9 的总数等于 2,这是 n = 50 时的最大可能值。