Start: 2025-07-11 17:45:00

暑假训练赛08

End: 2025-07-11 20:35:00
Now  2025-08-11 18:14:22  类型: IOI  状态: Ended 

P3. 修改数字
Description

白浅妹妹有一个很大的数字,她想让这个数字变得更大。有两种操作:

  1. 将数字的每一位都增加1,如果某一位是9,则会增加到0。这种操作可以使用无限次。

  2. 将数字的某一位增加1,如果某一位是9,则会增加到0。这种操作至多只能使用一次。

请问白浅妹妹最多能将这个数字变成多少。


Input

输入一个正整数n。

Output

输出一个正整数表示答案。

Examples

Input

320

Output

996

Input

290

Output

977

Input

89

Output

99
Hint

先进行6次操作1,变成986,然后对第二位进行一次操作2,变成996。


对于10%的测试点, n<10

对于20%的测试点,n<100

对于40%的测试点,有 n<10^{9}

对于60%的测试点,有n<10^{18}

对于100%的测试点,有 n<10^{100000}


Submit

题目参数
Time Limit 1 second
Memory Limit 128 MB
Submit