長さ $2$ の数列 $A = (0, 1)$ があります。この数列に対して、以下の $3$ 種類の操作が行えます。

• 操作 I (Increment)： $A$ の末尾の数を $x$ とします。 $A$ の末尾に $x+1$ を追加します。
• 操作 T (Twice)： $A$ の末尾の数を $x$ とします。 $A$ の末尾に $2x$ を追加します。
• 操作 F (Fibonacci)： $A$ の末尾から $2$ つの数を $x,y$ とします。 $A$ の末尾に $x+y$ を追加します。

shiba君は、数列 $A$ にいずれかの操作を $0$ 回以上行うことで、数列 $A$ の末尾を $N$ にしたいです。
ただし、shiba君は飽きっぽいので、同じ操作を $2$ 回連続で行うことはできません。

必要な操作回数の最小値を求め、最小値を達成する操作列を $1$ つ構築してください。
なお、この問題の制約下で、必要な操作回数の最小値は $10^5$ 以下であることが証明できます。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $2 \leq N \leq 10^{18}$
• $1 \leq T \leq 100$
• 入力される値はすべて整数

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

1. ($100$ 点)

• $2 \leq N \leq 10^5$

2. ($300$ 点)

• 追加の制約はない。

入力は以下の形式で標準入力から与えられる。

${\rm case}_i$ は $i$ 番目のテストケースを表す。各テストケースは以下の形式で与えられる。

$T$ 行出力せよ。 $i$ 行目には、 $i$ 番目のテストケースに対する最小の操作回数 $L$ と、操作列 $S$ を空白区切りで出力せよ。
操作列が複数存在する場合は、どれを出力してもよい。
ただし、操作列 $S$ は長さ $L$ の文字列であり、 $i$ 文字目 ( $1\leq i \leq L$ ) は $i$ 回目の操作に対応する英大文字で構成される。