問題文

K と P と - のみからなる長さ $N$ の文字列 $S$ が与えられます。以下、$S$ の先頭から $i$ $(1 \leq i \leq N)$ 番目の文字を $S_{i}$ と表します。
また、$S$ に含まれる文字のうち、少なくとも $1$ つは - でないことが保証されます。

これから、コアさんとパチェさんがゲームを行います。 コアさんから始めて、次の操作を交互に行います。

1. まず、次の条件をすべて満たす整数の組 $(x, y)$ を $1$ つ選ぶ。

• $1 \leq x \leq y \leq N$

• $x \leq i \leq y$ を満たす任意の整数 $i$ について、$S_{i}$ は - でない。

• $1 \leq i < x$ または $y < i \leq N$ を満たすある整数 $i$ が存在し、$S_{i}$ は - でない。

2. 次に、$x \leq i \leq y$ を満たす各整数 $i$ に対し、$S_{i}$ を - に置き換える。

上の操作 1 において、選べる整数の組 $(x, y)$ が存在しないとき、ゲーム終了となります。

そして、ゲーム終了時、$1 \leq i \leq N$ を満たす唯一つの整数 $i$ が存在し、$S_{i}$ は - でないことが証明できます。
この $S_{i}$ について、ゲームの結果を次のように決定します。

• $S_{i}$ が K ならば コアさんの勝ちとし、そうでないならばパチェさんの勝ちとする。

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

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

制約

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

• $1 \leq N \leq 5 \times 10^{5}$

• $S$ は K と P と - のみからなる長さ $N$ の文字列

• $S$ に含まれる文字のうち、少なくとも $1$ つは - でない

• $1$ つの入力で与えられる $N$ の総和は $5 \times 10^{5}$ 以下

• $S$ 以外の入力はすべて整数

入力

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

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

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

$N$
$S$

出力

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

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

サンプル

4
1
K
9
-PKP-P-KK
3
PPK
10
K-PK---P-K

K
P
K
K