题目描述

给你一串未加密的字符串 $str$，通过对字符串的每一个字母进行改变来实现加密，加密方式是在每一个字母 $str[i]$ 偏移特定数组元素 $a[i]$ 的量，数组 $a$ 前三位已经赋值：$a[0] = 1$，$a[1] = 2$，$a[2] = 4$。

当 $i \geq 3$ 时，数组元素 $a[i] = a[i-1] + a[i-2] + a[i-3]$。

例如：原文 $abcde$ 加密后 $bdgkr$，其中偏移量分别是 $1, 2, 4, 7, 13$。

输入描述

第一行为一个整数 $n$（$1 \leq n \leq 1000$），表示有 $n$ 组测试数据，每组数据包含一行，原文 $str$（只含有小写字母，长度 $0 < \leq 50$）。

输出描述

每组测试数据输出一行，表示字符串的密文。

样例1

输入

1
xy

输出

ya

说明

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