In the English language, nouns are inflected by grammatical number — that is singular or plural. In this problem we use a simple model of constructing plural from a singular form. This model doesn't always make English plural forms correctly, but it works in most cases. Forget about the real rules you know while solving the problem and use the statement as a formal document.
You are given several nouns in a singular form and your program should translate them into plural form using the following rules:
The first line of input contains a single positive integer n (1 ≤ n ≤ 10) — the number of words to be processed. The following n lines contain one word each. A word consists from 2 to 25 lowercase Latin letters. It is not guaranteed that the given words are real English words from vocabulary.
Print n given words in their plural forms on separate lines. Keep the words in the same order as they are given in the input.
## Input
The first line of input contains a single positive integer n (1 ≤ n ≤ 10) — the number of words to be processed. The following n lines contain one word each. A word consists from 2 to 25 lowercase Latin letters. It is not guaranteed that the given words are real English words from vocabulary.
## Output
Print n given words in their plural forms on separate lines. Keep the words in the same order as they are given in the input.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of contestants.
Let $ S_A \in \mathbb{Z}^+ $ be the score for problem A.
Let $ T = (T_1, T_2, \dots, T_N) $ be the sequence of total scores before system tests, with $ T_i \geq T_{i+1} $ for all $ i \in \{1, \dots, N-1\} $.
Let $ P = (P_1, P_2, \dots, P_N) $ be the sequence of probabilities that contestant $ i $'s solution fails system tests, with $ P_i \in [0.01, 1.00] $.
**Constraints**
1. $ 2 \leq N \leq 10^5 $
2. $ S_A \leq T_i \leq 10^5 $ for all $ i \in \{1, \dots, N\} $
3. $ T_i \geq T_{i+1} $ for all $ i \in \{1, \dots, N-1\} $
4. $ P_i $ is given with exactly two decimal digits, $ 0.01 \leq P_i \leq 1.00 $
**Objective**
Compute the expected number of pairs $ (i, j) $ with $ i < j $ such that:
- $ T_i > T_j $ before system tests,
- After system tests, contestant $ i $ loses $ S_A $ points with probability $ P_i $, contestant $ j $ loses $ S_A $ points with probability $ P_j $,
- And the new scores satisfy $ T_i - S_A \cdot X_i < T_j - S_A \cdot X_j $,
where $ X_i, X_j \sim \text{Bernoulli}(P_i), \text{Bernoulli}(P_j) $ are independent indicator variables for failure.
Define the indicator random variable for pair $ (i, j) $:
$$
I_{i,j} = \mathbb{1}_{\{T_i > T_j \text{ and } T_i - S_A \cdot X_i < T_j - S_A \cdot X_j\}}
$$
The expected number of swapped pairs is:
$$
\mathbb{E}\left[\sum_{1 \leq i < j \leq N} I_{i,j}\right] = \sum_{1 \leq i < j \leq N} \mathbb{P}(T_i > T_j \text{ and } T_i - S_A \cdot X_i < T_j - S_A \cdot X_j)
$$
Since $ T_i \geq T_j $ for $ i < j $, and $ T_i > T_j $ only when $ T_i \ne T_j $, we consider only pairs with $ T_i > T_j $. For such a pair, the event $ T_i - S_A \cdot X_i < T_j - S_A \cdot X_j $ occurs if and only if:
- $ X_i = 1 $ and $ X_j = 0 $,
because $ T_i - S_A < T_j $ is equivalent to $ T_i - T_j < S_A $, which is always true since $ T_i > T_j $ and $ T_i - T_j \leq S_A $ (as both scores are at least $ S_A $ and differ by at most $ S_A $ — actually, since $ T_i \geq S_A $, $ T_j \geq S_A $, and $ T_i > T_j $, the difference $ T_i - T_j $ can be any integer from 1 to $ 10^5 - S_A $, but the key is: **only when $ X_i = 1 $ and $ X_j = 0 $** does the inversion occur, because:
- If $ X_i = 0 $, $ X_j = 0 $: scores unchanged → $ T_i > T_j $ → no swap
- If $ X_i = 0 $, $ X_j = 1 $: $ T_i > T_j - S_A $, but since $ T_i \geq T_j $, and $ T_j - S_A \geq 0 $, we have $ T_i \geq T_j > T_j - S_A $ → still $ T_i > T_j - S_A $ → no swap
- If $ X_i = 1 $, $ X_j = 0 $: $ T_i - S_A < T_j $ → **swap occurs**
- If $ X_i = 1 $, $ X_j = 1 $: $ T_i - S_A $ vs $ T_j - S_A $ → same order as before → no swap
Thus, for each pair $ (i, j) $ with $ i < j $ and $ T_i > T_j $:
$$
\mathbb{P}(\text{swap}) = P_i \cdot (1 - P_j)
$$
Therefore, the expected number of swapped pairs is:
$$
\sum_{\substack{1 \leq i < j \leq N \\ T_i > T_j}} P_i (1 - P_j)
$$