98. Parenheses

0 Judge

Code: 0


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