题目描述

给你一串未加密的字符串 $str$ ，通过对字符串的每一个字母进行改变来实现加密，加密方式是在每一个字母 $str[i]$ 偏移特定数组元素 $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
xy

输出

ya

说明

第一个字符 $x$ 偏移量是 $1$ ，即为 $y$ ，第二个字符 $y$ 偏移量是 $2$ ，即为 $a$ 。