Count Distinct Strings

You are given a string consisting of lowercase English letters (a to z) and the wildcard character *. The wildcard can be replaced with any of the 26 lowercase English letters. Your task is to compute the total number of distinct strings that can be generated by replacing each * with any lowercase letter.

In particular, if a string contains k occurrences of *, then the answer is given by the formula: $$26^k$$. If there are no wildcard characters present, the number of distinct strings is 1.

inputFormat

The first line of input contains a single integer T (the number of test cases). Each of the following T lines contains a non-empty string consisting of lowercase English letters and the character *.

outputFormat

For each test case, output a line containing the number of distinct strings that can be generated by replacing every * with any letter from 'a' to 'z'.

1
a*

26