github.com/captn3m0/codechef.git

---
category_name: medium
problem_code: KOL1510
problem_name: 'The Revenge of Jalebi Bai'
languages_supported:
    - C
    - CPP14
    - JAVA
max_timelimit: '3'
source_sizelimit: '50000'
problem_author: admin2
problem_tester: null
date_added: 12-12-2015
tags:
    - acm15kol
    - admin2
    - backtracking
    - shortest
    - supersequence
editorial_url: 'http://discuss.codechef.com/problems/KOL1510'
time:
    view_start_date: 1451123700
    submit_start_date: 1451123700
    visible_start_date: 1451123700
    end_date: 1735669800
    current: 1493557724
layout: problem
---
All submissions for this problem are available.Jalebi Bai recently met her long time friend Barfi Tai. Instead of entertaining her guest, Barfi Tai kept boasting about her **K** marvelous necklaces made of black and golden beads. Jalebi Bai felt really jealous of it and decided to exact revenge.

She has invited Barfi to visit her home next week. Meanwhile, she is planning to buy a truly beautiful necklace to make Barfi jealous. According to her, a truly beautiful necklace should contain each of Barfi’s necklaces as a **subsequence** of it. Though still trying to show off, Jalebi Bai is smart and does not want to put a lot of money in it. So she wants to buy a truly beautiful necklace containing the minimum number of beads.

She goes to Devu Sunar and asks him to provide her such a necklace. Devu Sunar is busy this week and has asked you to help him in building the necklace. Please help him!

### Note

- A subsequence is a sequence that can be derived from another sequence by deleting some elements but without changing the order of the remaining elements. For example, the sequence \[A,B,D\] is a subsequence of \[A,B,C,D,E,F\].
- The bead patterns on the necklaces are **not** considered circular.

### Input

The first line of the input contains an integer **T** denoting the number of test cases. The description of **T** test cases is as follows.

The first line of each test case contains an integer **K** denoting the number of necklaces of Barfi.

**K** lines follow. Each of them contains a string made from the characters ‘B’ (representing black bead) and ‘G’ (representing golden bead), with the **i**th line denoting Barfi Tai's **i**th necklace.

### Output

For each test case, output a truly beautiful necklace with the minimum number of beads. If there are more than one such necklace, you are allowed to print any of them.

### Constraints

- **1** ≤ **T** ≤ **30**
- **1** ≤ **K** ≤ **16**
- **1** ≤ length of each necklace of Barfi ≤ **8**

### Example

<pre><b>Input:</b>
3
2
BG
GB
2
BGB
GG
3
BG
GBB
BGB
<b>Output:</b>
BGB
BGGB
BGBB
</pre>### Explanation

**In the first example**,
Devu can give necklace the BGB to Jalebi Bai, as it contains both the Barfi's necklace BG and GB as subsequence.
Note that Devu can also give GBG to Jalebi Bai.

**In the second example**,
Devu can give the necklace BGGB, as it contains both the Barfi's necklace BGB and GG as subsequence.
Note that there are many other possible truly beautiful necklaces of length 4, that Devu can give, e.g. BGBG or GBGB.
You are allowed to print any of them.

**In the third example**,
Devu can give the necklace BGBB or GBGB. You are print any of them as your answer.