C. Non-decreasing Groups
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string of digits. Divide it into one or more non-empty groups of consecutive digits. Every digit must belong to exactly one group.

Read each group as an integer. The groups must be in non-decreasing order: the value of each group must be greater than or equal to the value of the group before it.

For example, the string 1234 can be divided as 1 | 2 | 34. The group values are $$$1$$$, $$$2$$$, and $$$34$$$, so they are in non-decreasing order. This division has $$$3$$$ groups. Your task is to find the largest number of groups possible.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10000$$$), the number of test cases.

Each of the next $$$t$$$ lines contains a non-empty string $$$s$$$ consisting only of digits.

The length of each string does not exceed $$$300000$$$. The sum of the lengths of all strings does not exceed $$$300000$$$.

Output

For each test case, print the maximum number of groups.

Example
Input
4
1234
123
321
9000
Output
4
3
2
1