This is a communication problem.

After the Pb Informatics Olympiad hosted by Country P, you have been assigned to solve an important problem: mailing each contestant their competition score.

In this Pb Informatics Olympiad, each contestant's score can be represented as a non-negative integer $S$ in the range $[0, 10^{10})$. To send information to a contestant, you can specify at most $M$ pigeons and send them to the contestant. You can write exactly one digit on each pigeon (i.e., each pigeon can have any digit from 0123456789 written on it), so that the contestant can obtain one digit of information after seeing each pigeon.

Although you asked the organizers to take their time, the organizers are in a hurry and cannot tolerate sending the pigeons one by one. Therefore, they require that all pigeons be sent to the contestant simultaneously. Since the order of the pigeons is not fixed, the order relationship of all pigeons will be lost once the contestant receives the information from all of them.

Now, you need to develop appropriate strategies for the organizers and the contestant so that the contestant can successfully obtain their score.

Formal Problem Statement

The program Host has a non-negative integer $S$ strictly less than $10^{10}$. It can send at least one and at most $M$ integers between $0$ and $9$ to the program Participant, but the order of transmission will be shuffled by the interactor. Use an appropriate strategy so that Participant can recover the integer $S$.

Implementation Details

This is a communication problem; this problem only supports the C++ language.

You need to submit two programs. The program Host describes the strategy for the Host to send information to the Participant, and the program Participant describes the strategy for the Participant to recover the information.

Please note that each test case may contain multiple test data sets. In one test case, both programs will be required to answer $T$ independent queries.

Host

The first program you submit is Host, which describes the strategy for the Host to send information to the Participant.

You need to include the header file Host.h and implement the following function:

std::string Send(long long S);

• In each test case, this function will be called $T$ times.
• The meaning of the parameter $\texttt{S}$ is the $S$ in the problem statement.
• You need to return a string consisting only of digits $0 \sim 9$, describing the information sent by the host to the contestant. Please note that you cannot return an empty string.

Participant

The second program you submit is Participant, which describes the strategy for the Participant to recover the information.

You need to include the header file Participant.h and implement the following function:

long long Restore(std::string X);

• In each test case, this function will be called $T$ times.
• The meaning of the parameter $\texttt{X}$ is the string sent by the host, but the order may be shuffled.
• You need to return an integer $S$, describing the score recovered by the contestant.

Sample Interactor

The provided files for this problem contain a sample interactor grader.cpp. Contestants can use the following command to compile and obtain the executable file:

g++ Host.cpp Participant.cpp grader.cpp -o answer -O2 -std=c++14

The executable will read input data from standard input in the following format:

• The first line of input contains an integer $T$, representing the number of test data sets.
• For each data set, the input consists of a single line containing an integer $S$.

The executable will output the following data to standard output:

• If an error occurs during the communication process, the corresponding error message will be output.
• Otherwise, the first line of output contains the string OK, and the second line contains the maximum length $L$ of the strings you returned across all queries.

Please note that:

1. The sample interactor does not check whether the contestant's program uses illegal means to transmit information.
2. In the sample interactor, the strategy for randomly shuffling the string returned by the Send function is not fixed across runs. If you want to change it to a fixed strategy, you can modify the seed of the random number generator rng to a fixed value, for example:

std::mt19937 rng(123456);

During final evaluation, the programs Host and Participant will be compiled separately and run in two different processes. The time limit (1.0 second) and memory limit (256 MiB) for this problem refer to the maximum time and memory that each process can use. Exceeding these limits in either process will result in a corresponding error. It is guaranteed that during final evaluation, the interactor for each of the three programs will use no more than 0.2 seconds of time and 16 MiB of memory, meaning the contestant has at least 0.8 seconds of time and 240 MiB of memory available.

Please note that you do not need to, and must not, read any data from standard input or output any information to standard output, as this may cause the communication process to behave abnormally.

Examples

Input 1

7
0
1
2
42
998244353
1000000007
2333333333

Output 1

OK
L = 42

Note that the second line of the output represents the maximum length of the strings returned by the contestant, which may vary depending on the strategy you use.

Subtasks

Please note that the total score for this problem is 75 points.

For all data, $1 \le T \le 10^3$, $0 \le S < 10^{10}$.

In each test case, if you return an incorrect $S$ in any query, or if any other error occurs, your score will be $0$.

Otherwise, let $L$ be the maximum length of the strings you returned across all queries. Your score is related to the value of $L$:

Hack

The Hack feature is not available for this problem.