U263724 说“说‘说“你好！”！’！”！（Say “Say ‘Say “Hello!”!’!”!）
题目背景
> **不熟悉 C/C++ 编程语言的，建议仔细阅读此段。**
>
> 在 C/C++ 语言中，字符串常量用双引号对 `""` 括起来。在字符串常量中，双引号 `"` 用 `\"` 表示，换行符用 `\n` 表示，反斜杠 `\` 用 `\\` 表示。
>
> 例如字符串：
> ```
> "C:\Hello World.exe"
> Good morning!
> ```
> 表示成 C/C++ 语言的字符串常量为：
> ```c
> "\"C:\\Hello World.exe\"\nGood morning!"
> ```
---
通常在 C/C++ 语言中，如果我们要输出一个字符串，像这样（注意末尾有换行符）：
```
Hello!
```
我们会使用如下代码：
```c
printf("Hello!\n");
```
其中，换行符用 `\n` 替代。
代码本身也是一个字符串。如果要输出上面这行代码的内容，又该怎么做呢？
答案是：对于上述代码字符串，将反斜杠 `\` 全部替换成 `\\`，将双引号 `"` 全部替换成 `\"`，在整个字符串的前面加上 `printf("`，后面加上 `");`，得到如下代码：
```c
printf("printf(\"Hello!\\n\");");
```
运行这行代码，屏幕上将会显示如下内容：
```
printf("Hello!\n");
```
我们称 `printf("Hello!\n");` 为原字符串 `Hello!`（末尾带换行符）的输出嵌套，也称 $\bm 1$ **层输出嵌套**；`printf("printf(\"Hello!\\n\");");` 为原字符串的 $\bm 2$ **层输出嵌套**（$1$ 层输出嵌套的 $1$ 层输出嵌套）……以此类推。
类似地，`Hello!`（末尾带换行符）的 $\bm 3$ **层输出嵌套**为：
```c
printf("printf(\"printf(\\\"Hello!\\\\n\\\");\");");
```
上面只是以 `Hello!`（末尾带换行符）这个字符串举例，本题所涉及的字符串并不局限于此。
赵迪（Zaoly）对此非常感兴趣，想要编写程序判断一个字符串是否为正确的输出嵌套。
题目描述
下面定义字符串 $s$ 的 $\bm n$ **层输出嵌套**（$n=0,1,2,\ldots$）：
1. $s$ 是 $s$ 的 $0$ 层输出嵌套；
2. 对 $s$ 的 $n$ 层输出嵌套依次进行如下操作，所得字符串是 $s$ 的 $n+1$ 层输出嵌套：
1. 替换所有的 `\` 为 `\\`；
2. 替换所有的换行符为 `\n`；
3. 替换所有的 `"` 为 `\"`；
4. 在最前面添加 `printf("`；
5. 在最后面添加 `");`。
给定一个字符串 $S$，请判断是否存在原字符串 $s$ 和整数 $n$，使得 $S$ 是 $s$ 的 $n$ 层输出嵌套。已知原字符串 $s$ 除最后一个字符外，仅由 ASCII 编码从 $32$ 到 $126$ 之间的字符组成（**除了百分号 `%`**，ASCII 编码为 $37$），且**最后一个字符是换行符**（ASCII 编码为 $10$）。
### **注意：**
1. 前缀 `printf("` 和后缀 `");` 中的括号、引号和分号不能遗漏；
2. `printf` 中每个字母必须**小写**，`\n` 中的字母也必须**小写**；
**（以下条目尤其针对懂 C/C++ 语言的）**
3. 不考虑 C/C++ 语言的多行字符串语法；
4. 不考虑本题未提到的 C/C++ 语言转义字符。
输入格式
**本题包含多组测试数据。**
第一行包含一个整数 $T(1\le T\le20000)$，表示测试数据的组数。
每组测试数据的格式如下：
一行一个字符串 $S$，长度 $l$ 为满足 $1\le l\le2000$ 的整数，每个字符的 ASCII 编码 $a$ 均为满足 $32\le a\le126$ 且 $a\ne37$（对应字符 `%`）的整数，以换行符结束。**末尾换行符忽略**，不算进字符串 $S$ 中。
所有测试数据的字符数总和小于 $10^7$。
输出格式
输出 $T$ 行，每组测试数据输出一行，内容如下：
- 如果 $S$ 是某原字符串 $s$ 的 $n$ 层输出嵌套，则为整数 $n$ 的值；
- 否则，为“`-1`”。
说明/提示
**【样例解释】**
**样例二**：解输出嵌套后所得字符串为（末尾带换行符）：
```
Love
It!
```
中间出现换行符，不符合要求。
**样例三**：解输出嵌套后所得字符串仅包含换行符，符合要求。
**样例四**：解输出嵌套后所得字符串为：
```
printf("\t\n");
```
其中 `\t` 无法通过输出嵌套变换方法得到，无法继续解输出嵌套。
**样例七**：解输出嵌套后所得字符串为：
```
printf("Nice to meet you!\n);
```
其中双引号不匹配，无法继续解输出嵌套。
**样例八**：解输出嵌套后所得字符串为（末尾带换行符）：
```
printf("Good night!\n");
```
因为最后一个字符是换行符，所以不能继续解输出嵌套，只能到此为止。恰巧最后一个字符是换行符，符合原字符串要求。
**样例九**：该字符串无法通过输出嵌套变换方法得到，因为在第 $109$ 个字符处出现了意外的双引号。
---
**【提示】**
ASCII 编码从 $32$ 到 $126$ 的字符依次为：
```
!"#$%&'()*+,-./0123456789:;?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
`abcdefghijklmnopqrstuvwxyz{|}~
```