Description

瓦徳老鼠很喜欢字母，他们拥有一个无限循环的字母表，如下： a b c d e f g h i j k l m n o p q r s t u v w x y z a b c d e f g h i j k l m n o p q r s t u v w x y z a b c d e f g h i j k l m n o p q r s t u v w ... 瓦徳老鼠很调皮，它每时每刻都在按照某一规则变幻着自己的位置（防止你抓住他）： 它在某一个初始位置字母a上，之后每秒都会向前跳K步到相应字母，如： 'n'每一时刻会向前跳3步，第一时刻变为'q',第二时刻变为't'..... 'w'每一时刻会向前跳2步，第一时刻变为'y',第二时刻变为'a'..... 现在给定瓦徳老鼠所在的位置字母a,以及向前跳的步数K，问经过T时刻，瓦徳老鼠在哪一个字母上？

Format

Input

第一行询问数n(0<n<=100) 接下来n行询问，每行给出一个字母a['a'..'z']，向前跳的步数K和时刻T

Output

共n行，每行对应一个询问的答案

Samples

3
a 2 2
n 3 1
n 3 2

e
q
t

Limitation

对于30%的数据：0<=K,T<=10000

对于100%的数据：0<=K,T<=10^16.