题目描述

紫悦掌握了友谊魔法，当字符串中出现连续子串 friendship 时，便会触发魔法消除，将这段字符串彻底消除。

魔法洗礼规则：

1. 字符串中所有连续的 friendship 都会被魔法消除；
2. 消除后字符串的前后部分会自动拼接，若新字符串再次形成连续的 friendship，魔法消除将持续触发，直到字符串中不再存在可消除的子串为止；
3. 剩余的字符串即为最终结果。

紫悦现在不想亲自施展友谊魔法，请你帮她计算：任意字符串经过友谊魔法洗礼后，最终会变成什么样子？

输入格式

第一行输入一个整数 $T$，表示测试用例组数；

接下来 $T$ 行，每行输入一个非空仅包含小写字符的字符串 $s$。

输出格式

对于每个测试用例，输出一行字符串，表示友谊魔法后的最终字符串，若为空则输出 -1。

3
friendxship
friendshipismagic
friendfriendshipship

friendxship
ismagic
-1

数据范围

• 对于 $20\%$ 的评测用例，$|s|≤2000$;
• 对于所有评测用例，$1 \leq T \leq 3,|s|≤2*10^6$，$|s|$ 表示 $s$ 的长度。