AT_abc434_f [ABC434F] Concat (2nd)

You are given $ N $ strings $ S_i $ consisting of lowercase English letters. For all possible permutations $ P=(P_1,P_2,\dots,P_N) $ of $ (1,2,\dots,N) $ , write down the string generated as follows: - Concatenate $ S_{P_1},S_{P_2},\dots,S_{P_N} $ in this order. Let $ A_1,A_2,\dots,A_{N!} $ be the sequence of the $ N! $ written strings sorted in lexicographical order. Output $ A_2 $ . You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 This input contains three test cases. For the first test case, $ S=( $ `abc`, `ac`, `ahc` $ ) $ . We have $ A=( $ `abcacahc`, `abcahcac`, `acabcahc`, `acahcabc`, `ahcabcac`, `ahcacabc` $ ) $ , so output $ A_2= $ `abcahcac`. ### Constraints - $ 1 \le T \le 1.5 \times 10^5 $ - $ 2 \le N \le 3 \times 10^5 $ - $ T,N $ are integers. - $ S_i $ is a string consisting of lowercase English letters with length between $ 1 $ and $ 10^6-1 $ , inclusive. - For a single input, the sum of $ N $ does not exceed $ 3 \times 10^5 $ . - For a single input, the sum of $ |S_i| $ does not exceed $ 10^6 $ .