Borussia Dortmund are a famous football ( soccer ) club from Germany. Apart from their fast-paced style of playing, the thing that makes them unique is the hard to pronounce names of their players ( błaszczykowski , papastathopoulos , großkreutz etc. ).
The team's coach is your friend. He is in a dilemma as he can't decide how to make it easier to call the players by name, during practice sessions. So, you advise him to assign easy names to his players. A name is easy to him if
1. It consists of only one word. 2. It consists of only lowercase english letters. 3. Its length is exactly . 4. It contains exactly different letters from the letters of English alphabet. 5. At least one of its proper prefixes matches with its proper suffix of same length.
Given, and you have to tell him the number of easy names he can choose from modulo .
Note : A prefix of a name is proper if, . Similarly, a suffix of a name is proper if, .
The first line of the input will contain ( the number of testcases ).
Each of the next lines will contain space separated integers and .
For each testcase, output the number of ways the coach can assign names to his players modulo .