The sorcerer Bajtazar has finally, after many years, found the text of a ritual that can summon the Great Binary Imp to answer the eternal question of humanity: $P = NP?$. However, to complete the ritual, it is necessary to recite the full name of the Imp, which Bajtazar does not know. It is only known that the name is a word consisting of exactly 100 characters. As befits a Binary Imp, these are exclusively the characters 0 and 1.

Bajtazar can attempt the ritual multiple times (but no more than 222 times, after which his old alchemical apparatus will finally fail). If he speaks the correct name of the Imp even once, the ritual will succeed, and world computer science will change forever. Thanks to his magical intuition, Bajtazar will know exactly how many characters of the Imp's name he spoke correctly after each attempt. There is, however, an additional complication: the Imp is an extremely capricious creature and sometimes changes its mind about what its name is. More precisely, after each failed attempt by Bajtazar, the Imp draws a number $k$ from the set $\{0, 1, \dots, 99\}$ with a uniform distribution. If it turns out that the $k$-th character was spoken correctly by Bajtazar in that attempt, the Imp will immediately change it in its name to the opposite (0 to 1, and 1 to 0).

As the sorcerer's unlucky apprentice, you must help him guess the Imp's name – do it quickly, otherwise the furious Bajtazar might turn you into... well, something nasty. For example, a fire hydrant. And be glad he isn't trying to summon the Very Great Hexadecimal Imp.

Interaction

To solve the task, you must include the following directive at the beginning of your program:

#include "cho.h"

The library provides only one function:

int recytuj(const std::string& proba);

which works as described above – if the string proba is identical to the Imp's true name, your program will terminate immediately and be accepted on that test. If not, the function returns a number (between 0 and 99) equal to the number of characters matching the true name, and additionally, a fragment of code similar to the following is executed:

int k = rand() % 100; // The actual library implementation does not use the rand() function.
if(proba[k] == prawdziwe_imie[k])
flip(prawdziwe_imie[k]);

where prawdziwe_imie denotes the (secret) name of the Imp, and flip() changes the corresponding character from 0 to 1 and vice versa.

For each query, proba must be a string consisting of exactly 100 characters, each 0 or 1. You also cannot call the recytuj() function more than 222 times – if you break any of these rules, you will receive a Wrong Answer message.

The initial name of the Imp is set at the beginning of each test.

Implementation Details

A package with useful files is available in the Files section on SIO, containing a sample library chozaw.cpp that implements the function mentioned above.

To compile your program (let's say, cho.cpp) with this library, enter the following command:

g++ cho.cpp chozaw.cpp -o cho -std=c++11 -O2

Input

The library accepts input in the following format: The first and only line should contain the Imp's name, consisting of 100 characters 0 or 1.

Examples

Input 1

101010

Output 1

recytuj("010010") -> 3
recytuj("001111") -> 4
recytuj("101110") -> 6

Note

For simplicity, assume the Imp's name has a length of 6. This assumption applies only to this example, and such a test will not appear in the test suite. Let the Imp's name be 101010. Let's say the drawn position $k$ is 3 in the first call and 0 in the second.