B. Beautiful Strings
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Let's define that a string $$$s$$$ is considered better than another string $$$t$$$ if and only if both of the following conditions are met:

  • $$$s$$$ is not a prefix of $$$t$$$
  • $$$s$$$ is lexicographically smaller than $$$t$$$

Alice has a string $$$s$$$ of length $$$N$$$. She wants to split the string into $$$K$$$ continuous substrings $$$s[1 : p_1], s[p_1 + 1 : p_2], \dots, s[p_{K - 1} + 1 : p_K]$$$ such that:

  • Define $$$p_0 = 0$$$
  • For every $$$1 \leq i \lt K$$$, the substring $$$s[p_{i - 1} + 1 : p_i]$$$ is better than the substring $$$s[p_i + 1 : N]$$$
  • $$$p_K=N$$$
Input

The first line of input contains a single integer $$$T$$$ denoting the number of test cases.

Each test case consists of a single line containing a lowercase letter string $$$s$$$.

  • $$$1 \leq T \leq 2\times 10^5$$$
  • $$$1 \leq |s| \leq 2\times 10^5$$$
  • The total length of all strings across all test cases will not exceed $$$2\times 10^5$$$ characters.
Output

For each test case, output the maximum possible value of $$$K$$$.

Example
Input
2
abababa
aababaddb
Output
2
4