Splitting a Hexadecimal String

Consider splitting a string S of length n into k substrings T1, T2, ..., Tk under the following conditions:

• 1 ≤ k ≤ n
• For each i with 1 ≤ i ≤ k, the substring Ti has length at least 1 and is a substring of S. That is, it consists of consecutive characters of S.
• Concatenating T1, T2, ..., Tk in order gives back the original string S.

For example, when S = "FED", there are 4 ways to split it:

• Way 1: T1 = "FED" (here k = 1)
• Way 2: T1 = "F", T2 = "ED" (here k = 2)
• Way 3: T1 = "FE", T2 = "D" (here k = 2)
• Way 4: T1 = "F", T2 = "E", T3 = "D" (here k = 3)

A string of length n can be split in 2n-1 ways under these conditions.

In this problem, the original string S is a hexadecimal number consisting only of 0-9 and A-F.

Albert wants to know how many ways there are to split S under the above conditions so that T1, T2, ..., Tk form a non-decreasing sequence. Specifically, after splitting S, he wants the hexadecimal values represented by the substrings to satisfy T1 ≤ T2 ≤ ... ≤ Tk.

For the example above, the sequences produced by the four ways are as follows:

• Way 1: [FED(16) = 4077] (non-decreasing)
• Way 2: [F(16) = 15, ED(16) = 237] (non-decreasing)
• Way 3: [FE(16) = 254, D(16) = 13]
• Way 4: [F(16) = 15, E(16) = 14, D(16) = 13]

Here the non-decreasing sequences come from ways 1 and 2, so the answer is 2.

As another example, when S = "0070", the following 4 ways are possible.

• Way 1: T1 = "0070"
• Way 2: T1 = "0", T2 = "0", T3 = "70" (here [0, 0, 70(16) = 112])
• Way 3: T1 = "00", T2 = "70"
• Way 4: T1 = "0", T2 = "070"

As ways 1, 3, and 4 show, substrings may contain leading zeros.

Given a hexadecimal string S as input, find how many ways Albert can split S into substrings to obtain a non-decreasing sequence.

The first line gives the number of test cases T.

Each of the next lines gives a string S.

The characters making up S are only 0-9 and A-F, which are used in hexadecimal.

For each test case, print the answer on its own line.

• 1 ≤ T ≤ 20
• 1 ≤ n ≤ 15
• The characters making up S are only 0-9 and A-F