98. Parenheses

Parenheses

題目敘述

給一個字串 $s$，裡面字元只有 ()?，因為標題削掉了一個字元，你也可以選擇把其中一個字元削掉（也可以選擇不用），接著回答有沒有可能把?字元全部填入左或右括弧()使得該字串變成合法的括弧(Parentheses)匹配

$$ |s| \leq 10^5 $$

50% Credit for $|s| \leq 2000$

Note

一個只有 () 字元的字串是合法的括弧匹配，如果他任何前綴 ( 的數量不少於 ) 的數量，而且該字串 () 的數量相同，空字串算合法括弧匹配

輸入

第一行有一個數字 $T$, $T \leq 5$ 代表測資數量

接下來每一行有一個目標字串 $s$

輸出

對於每一個目標字串輸出一行

如果有可能在削掉字元（或什麼都不做）之後得到成功填入()變成合法字串請輸出 Eevee 否則輸出 Pikachu

Sample Input

3
(??)
((?
((

Sample Output

Eevee
Eevee
Pikachu

說明

1. 可以構造 ()()
2. 把第一個字元削掉之後，可以構造 ()
3. 只有可能是不合法括弧匹配

Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 22