Lucky Ticket

Interview

Time limit2sMemory limit128 MB

Summary

Find the longest even-length substring of a digit string whose first half digit sum equals its second half digit sum.

Level: Easy3 of 10
Topics: Prefix sum, Brute force, String, Array
Solved: No attempts yet

Problem

A baseball team gives each visitor a numbered ticket. A ticket has length exactly 2N. If the sum of the first N digits equals the sum of the last N digits, the ticket is called lucky.

Given a digit string S, find the longest contiguous substring that could be a lucky ticket. Output that maximum length.

Input

The first line contains S. S consists only of digits from 1 through 9, and its length is a positive integer not greater than 50.

Output

Output the maximum length of a contiguous substring of S that satisfies the lucky-ticket rule. If no such substring exists, output 0.

Examples5

Example 1
Input
```
74233285
```
Expected output
```
4
```
Example 2
Input
```
123231
```
Expected output
```
6
```

Example 3

Input

986561517416921217551395112859219257312

Expected output

Example 4
Input
```
1
```
Expected output
```
0
```
Example 5
Input
```
112
```
Expected output
```
2
```