B. Minor Reduction time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

You are given a decimal representation of an integer xx without leading zeros.

You have to perform the following reduction on it exactly once: take two neighboring digits in xx and replace them with their sum without leading zeros (if the sum is 0, it's represented as a single 0).

For example, if x=10057, the possible reductions are:

• choose the first and the second digits 1 and 0, replace them with 1+0=1; the result is 1057;
• choose the second and the third digits 0 and 0, replace them with 0+0=0; the result is also 1057;
• choose the third and the fourth digits 0 and 5, replace them with 0+5=5; the result is still 1057;
• choose the fourth and the fifth digits 5 and 7, replace them with 5+7=12; the result is 10012.

What's the largest number that can be obtained?

Input

The first line contains a single integer tt (1≤t≤104) — the number of testcases.

Each testcase consists of a single integer x (10≤x<10^200000). x doesn't contain leading zeros.

The total length of the decimal representations of x over all testcases doesn't exceed 2⋅10^5.

Output

For each testcase, print a single integer — the largest number that can be obtained after the reduction is applied exactly once. The number should not contain leading zeros.

Example input

2
10057
90

output

10012
9

Note

The first testcase of the example is already explained in the statement.

In the second testcase, there is only one possible reduction: the first and the second digits.

 

 题目分析：题目给定我们一个整数x，但是数据特别大，要求我们求这个x的两个位数相加替代这两位后能构成的最大的值。

　　　　

　　首先这是一个大整数x，我们考虑用字符串来解决问题，其次我们分析，

　　如果这个数中有两个位数相加大于等于10的情况

　　我们取哪两位才能构成最大的

　　比如18920

　　如果我们取8 9 构成17，得到x = 11720

　　如果我们取9 2 构成11，得到x= 18110

　　明显大于取前面的吧？为什么，因为我两个数相加最多不超过二十啊，如果取前面的数相加，那么损失的一定会比取后面的要多

　　

　　接下来我们分析不能得到10以上的情况

　　比如说110

　　取1 + 1   和1 + 0

　　这两种情况得到的数分别为20 和 11

　　很明显是20大吧，这种情况下我们就取最前面的两个数相加就可以了。

 

　　代码实现

　　

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int maxn = 2 * 1e5;
 4 char a[maxn + 10];
 5 int main()
 6 {
 7     int t;
 8     cin >> t;
 9     while(t--){
10         cin >> a;
11         int mc,mc1;
12         mc = mc1 = -1;
13         for(int i = 0;i < strlen(a) - 1;i++)
14             if(a[i] - '0' + a[i + 1] - '0' >= 10)
15                 mc = i,mc1 = i + 1;
16         if(mc1 == - 1 || mc == -1){//这里就是说没有出现大于等于10的情况
17             a[0] = (a[0] - '0' + a[1] - '0') + '0';
18             strcpy(a + 1,a + 2);
19         }
20         else {
21             int m = (a[mc1] - '0'+ a[mc] - '0');//大于等于10的情况
22             a[mc] =  m / 10 + '0';
23             a[mc1] = m % 10 + '0';                                                                                                     
24         }
25         cout << a << endl;
26     }
27     return 0;
28 }