Affine Cipher

Time Limit : 1 sec, Memory Limit : 65536 KB

アフィン暗号

簡単な暗号法の一つに、アフィン暗号というものがあります。まず、アルファベット a〜z を a = 0, b = 1, c = 2,..., x = 23, y = 24, z = 25 と 0〜25 の数字に置き換えます。そして、以下の式で、原文のアルファベットを置換します。

$F(\gamma) = (\alpha \cdot \gamma + \beta)$ mod $26$

ただし、mod 26 は 26 で割った余りを表します。例えば、$\alpha = 3, \beta = 2$ のとき、アルファベットの 'a' (=0) は、$F(0) = (3 \cdot 0 + 2)$ mod $26 = 2$ で 'c' に、アルファベットの 'n' (=13) は $F(13) = (3 \cdot 13 + 2)$ mod $26 = 15$ で 'p' に置換されます。 このとき、$\gamma$ に対する $F(\gamma)$ が必ず 1 対 1 で対応付けられるように、$\alpha$ と $\beta$ は慎重に選ばれているものとします($\alpha$ と 26 が互いに素であることが条件)。$\alpha = 4, \beta = 7$ のときのように、$F('a') = 7, F('n') = 7$ と、'a' も 'n' も同じ 'h' に置換されるようなことはありません。また、アルファベット以外の文字は置換されません。

暗号化された文字列を元の文章に復号したものを出力するプログラムを作成してください。元の文章には、キーワードとして

that
this

のいずれかが必ず含まれているものとします。

Input

複数のデータセットが与えられます。1行目にデータセット数 $n$ ($n \leq 30$) が与えられます。続いて $n$ 行のデータが与えられます。各データセットに英小文字と空白からなる 256 文字以内の暗号化された文章が1行に与えられます。

Output

各データセットに対して、復号した元の文章を1行に出力して下さい。

Sample Input

1
y eazqyp pnop pngtg ye obmpngt xmybp mr lygw

Output for the Sample Input

i submit that there is another point of view

Source: PC Koshien 2004 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2004
http://www.pref.fukushima.jp/pc-concours/