問題文

池の上に $1, 2, \dots, N + 1$ の番号が付いた $N + 1$ 個の足場が浮かんでいます。ここで、$N \geq 1$ とします。

これから、コアさんとパチェさんがゲームを行います。 最初、両者は足場 $N + 1$ の上にいます。
コアさんから始めて、次の操作を交互に行います。

1. まず、$1$ 以上 $N$ 以下の整数 $i$ を $1$ つ選ぶ。

2. 次に、足場 $N + 1$ から足場 $i$ にジャンプで移動する。

3. 次に、$x = i$ として足場 $N + 1$ に移動するまで次の操作を繰り返す。

• $x$ に $i$ を加算し、現在自分がいる足場から足場 $\min(x, N+1)$ にジャンプで移動する。

4. 最後に、足場 $i$ を遠隔操作によって破壊する。

両者のうち、先に上記の過程で次の条件のうち少なくとも $1$ つを満たした方の負けとします。

• 操作 1 開始時点で、$N$ 個の足場 $1, 2, \dots, N$ のうち足場 $1$ のみが破壊されていない。

• 操作 2 または操作 3 において、移動先の足場が既に破壊されている。

両者が最善を尽くしたとき、どちらが勝つか判定してください。

$T$ 個のテストケースについて答えを求めてください。

制約

• $1 \leq T \leq 10^{5}$

• $1 \leq N \leq 10^{12}$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
  $\vdots$
$\mathrm{case}_{T}$

各テストケースは次の形式で与えられます。

$N$

出力

答えを $1$ 行ずつ合計 $T$ 行に出力してください。

$i$ $(1 \leq i \leq T)$ 行目には、$i$ 個目のテストケースについてゲームを行ったときにコアさんが勝つならば K を、パチェさんが勝つならば P を出力してください。

サンプル

4
1
6
2023
1000000000000

P
K
K
K