J. C-Style String Length
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are analyzing a string literal written in the C programming language. In C, special characters inside string literals are represented using escape sequences, all of which begin with a backslash (\).

Some relevant escape sequences are:

  • \\: represents a single backslash character \
  • \ 0: represents the null character (NUL). In C, the function strlen stops counting characters when it encounters the first NUL.

You are given a string $$$S$$$, which represents the characters written inside the quotation marks of a C string literal. The string $$$S$$$ consists only of two characters: backslash (\) and zero (0).

Your task is to determine the value that the C function strlen would return after interpreting all escape sequences in $$$S$$$. If $$$S$$$ contains an incomplete escape sequence (i.e., a single backslash at the end of the string), then $$$S$$$ is considered INVALID, and you should report that instead.

The string $$$S$$$ is scanned from left to right according to the following rules:

  • If the current character is 0 and it is not part of an escape sequence, it is treated as a normal character and contributes $$$1$$$ to the string length.
  • If the current characters form the escape sequence \\, they produce a single backslash character and contribute $$$1$$$ to the string length.
  • If the current characters form the escape sequence \ 0, they produce a NUL character. At this point, strlen stops immediately, and the NUL character is not counted.
  • If any escape sequence is incomplete, and the string is considered INVALID.
Input

The first line contains a single integer $$$T \: (1 \le T \le 10^5)$$$ — the number of test cases.

Each test case consists of a single string $$$S \: (1 \le |S| \le 10^5)$$$, containing the characters \ and 0 — the string literal inside the quotation marks passed as a parameter to strlen.

It is guaranteed that the sum of $$$|S|$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer in a line — the value returned by strlen after decoding the string. If the string is not valid, output INVALID instead. Note that the output is case-sensitive.

Example
Input
4
\\\\
\\0
\0\\00
\\\
Output
2
2
0
INVALID
Note

In the first test case, \\\\ decodes to \\, so the length is $$$2$$$. In the second test case, \\ 0 decodes to \ followed by 0, so the length is $$$2$$$. In the third test case, \ 0\\ 00 begins with a NUL character, so strlen returns $$$0$$$. In the fourth test case, \\\ ends with an incomplete escape sequence, so it is INVALID.