+ **Time limit:** 1 second
+ **Memory limit:** 256 MB
Each CodeStar fan has gifted a phone number to the bootcamp. We want to store all these phone numbers, but the problem is that each number is written in a different format, and we need to store them in a uniform way.
Each gifted phone number falls into one of the following categories:
+ **Category 1:** starts with `09` and exactly 11 digits.
+ **Category 2:** starts with `98` and exactly 12 digits.
+ **Category 3:** starts with `+98`and exactly 12 digits.
+ Numbers that are **invalid**.
You are asked to convert all valid gifted phone numbers to **Category 3 format** so that we can store them easily. A number is considered valid if it belongs to one of Categories 1–3.
# Input
The first line of input contains a natural number $n$. Then, each of the next $n$ lines contains a string $s$ representing a gifted phone number.
It is guaranteed that each string contains only digits and the `+` character.
# Output
Your output should contain $n$ lines. For each line, if the corresponding phone number is valid, print it in **Category 3 format**; otherwise, print `invalid`.
# Examples
## Sample Input 1
```
5
09123456789
0912345678+9
+989123456789
091234567891
989123456789
```
## Sample Output 1
```
+989123456789
invalid
+989123456789
invalid
+989123456789
```
**Explanation:**
+ `09123456789` is valid and in Category 1; it should be converted to Category 3 format: `+989123456789`.
+ `0912345678+9` has a `+` in the middle of digits, so it is invalid.
+ `+989123456789` is already in correct Category 3 format.
+ `091234567891` has one extra digit, so it is invalid.
+ `989123456789` is valid in Category 2 and should be converted to Category 3 format: `+989123456789`.
+ **Time limit:** 1 second
+ **Memory limit:** 256 MB
Grandmother wants to grow **sprouted greens**. She has set aside $k$ lentil seeds and prepared a tray with $n$ suitable positions for the seeds. The positions are numbered from left to right from $1$ to $n$. The seeds must be planted with proper spacing, and each position can hold at most one seed.
|  |
|:---------------------------------------------------------------:|
| Sabzeh symbolizes vitality and growth. |
If two seeds are planted in consecutive positions, their growth will be hindered. Grandmother wants to place $k$ seeds in $n$ positions so that the number of such consecutive pairs is minimized. In other words, she wants to plant the seeds so that the number of integers $i$ with $1 \leq i \leq n-1$ for which both positions $i$ and $i+1$ have seeds is as small as possible.
Grandmother needs your help to calculate this minimum number.
# Input
The first line contains two integers $n$ and $k$, respectively.
# Output
Print a single line containing the **minimum number of consecutive position pairs** that have seeds in both positions.
# Examples
## Sample Input 1
```
5 2
```
## Sample Output 1
```
0
```
**Explanation:**
Grandmother can plant her two seeds in positions 1 and 4. No two seeds are adjacent.
## Sample Input 2
```
5 4
```
## Sample Output 2
```
2
```
**Explanation:**
Grandmother can plant her four seeds in positions 1, 2, 3, and 5. The adjacent pairs are $(1,2)$ and $(2,3)$, so the minimum number of consecutive pairs with seeds is 2.