The Honmoon is damaged! Or maybe it isn't. Can you help identify how much damage was done?

Specifically, the state of the Honmoon is encoded in a string, the ~honmoonSignature~. The signature of the Honmoon should normally be gold repeated some number of times, but the current signature has been damaged and some characters have gone missing. Compute the minimum number of characters that need to be inserted such that the augmented signature is gold repeated some number of times.

Constraints

~1 \le numTests \le 10^6~

~honmoonSignature~ will only have letters that are from gold.

The sum of the lengths of all ~honmoonSignature~s will be at most ~10^6~.

Subtask 1 [1 point]

The shortest possible augmented signature will be gold.

Subtask 2 [1 point]

No additional constraints.

Input Specification

The first line contains a single integer, ~numTests~.

The next ~numTests~ lines each contain a nonempty string of lowercase letters, ~honmoonSignature~, indicating the current signature of the Honmoon.

Output Specification

Output ~numTests~ lines, one per test case. For a given test case, output the minimum number of characters that need to be inserted such that the augmented signature is gold repeated some number of times.

Sample Input 1

2
gold
gd

Sample Output 1

0
2

Sample Explanation 1

In the first test case, no characters need to be inserted. In the second one, we need to insert one o and one l.

Sample Input 2

1
ggoolldd

Sample Output 2

12

Sample Explanation 2

We can show that goldgoldgoldgoldgold is the shortest possible augmented signature. This requires 12 additions.

This will be the first test case in the second subtask.