小慕正在处理一个字符串加密项目。他拿到一串未加密的字符串str，需要通过对每个字符进行偏移来加密。加密规则是：对于字符串中的第 i 个字符 str[i]，偏移量为数组 a 中对应位置的元素 a[i]。数组 a 的前三个元素已经确定：a[0]=1, a[1]=2, a[2]=4。当 i>=3 时，数组元素 a[i] = a[i-1] + a[i-2] + a[i-3]。例如，原文 "abcde" 加密后变为 "bdgkr"，对应的偏移量依次为 1, 2, 4, 7, 13。
提示：带虚线的词点一下有通俗解释。
输入描述
第一行为一个整数n (1 <= n <= 1000)，表示有n组测试数据，每组数据包含一行，原文str(只含有小写字母，0 < 长度 <= 50)。
输出描述
每组测试数据输出一行，表示字符串的密文
示例
示例 1
输入
1 xy
输出
ya
说明：第一个字符x偏移量是1，即为y，第二个字符y偏移量是2，即为a。
时间限制 1000 ms · 内存限制 128 MB