Car Selection

Alice and Bob are two friends. They want to buy two cars, one for Alice and one for Bob. That's why they come to a car shop. Alice wants to move faster. So, she wants to purchase the fastest car. On the other hand, Bob wants safety first. So, he wants to purchase the slowest car. They also want to spend the least money possible. So, if multiple cars are fulfilling their speed requirement, they will choose the one among them that has the lowest $Price$.

At first, there is no car in the shop. When a car arrives, its speed $X$ will be given. Let’s define, $F(X) =$ summation of each digit of $X$ and $G(X) =$ multiplication of ($1+$ each digit of $X$). For example, $F(355)=3+5+5=13$ and $G(355)=(1+3)\times (1+5)\times (1+5)=144$.

The cars have $Points$ based on the values of $F(x)$ and $G(x)$ where $Points = F(X)\times G(X)$. If a car arrives and this is the only car in the shop then $Price$ of the car is equal to the $Points$ of the car. Otherwise, $Price$ is the minimum absolute difference between the $Point$ of the selected car and the other existing cars in the shop. $Price$ of a car is defined as soon as the car arrives in the shop.
For example, if the $Points$ of the cars existing in the shop are: $[50, 24, 18, 90, 10]$ and a car of $Point\space 20$ is arrived, then the $Price$ of the car will be: $|18-20| = 2$, as this is the minimum absolute difference between the $Point$ of the car and the other existing cars in the shop.

You are given an integer $Q$. You have to perform total $Q$ queries of $3$ types. They are:

Query type $1$:
$1$ $X$
A new car arrives at the shop whose speed is $X$

Query type $2$:
$2$
Alice wants to purchase a car. Tell her the price of the car she will purchase.

Query type $3$:
$3$
Bob wants to purchase a car. Tell him the price of the car he will purchase

Once Alice or Bob will purchase a car, that car will be removed from the shop. If there is no car to purchase output $-1$.

Input

Input may contain several test cases. At first, you will be given an integer $T$, the number of test cases.
Each test case will start with an integer $Q$, the number of queries. Then each query will follow. In the case of query type 1, you will be given an integer $X$ which is the speed of the car.

Constraints:
$1 \leq T \leq 10^5$
$1 \leq Q \leq 10^6$
$1 \leq X \leq 10^9$
The summation of $Q$ in all test cases will not exceed $10^6$.

Output

In each test case, at first print “Case $x$:” in a separate line where $x$ is the case number starting from $1$. Then for each query of types $2$ and $3$, print the desired answer in a new line.

Sample

Input	Output
1 10 1 200 1 100 1 200 3 1 10 2 1 10 3 3 2	Case 1: 4 0 0 4 6