Question 1:
You are given a group of distinct k characters (from [a-z]). Construct a string of length n such that:

• No two consecutive positions in string contain the same character
• The odd positions can only contain characters from initial group of k characters
• Even positions can contain any character from a to z.

Indexing is 1 based. Find number of distinct ways to form such strings modulo 10^9+7.

Constraints:

• 0 < T <= 250
• 0 < n <= 100000
• 0 < k <= 26

Time limit: 0.5 sec

Example 1:

Input: n = 1, chars = ['a', 'b']
Output: 2

Example 2:

Input: n = 2, chars = ['a']
Output: 25

Question 2:
Given two numbers L and R. Determine count of numbers in range [L, R] such that their number of divisors is prime.

Constraints:

• 1 <= T <= 1000000
• 1 <= L <= 5000000
• 1 <= R <= 5000000
• L <= R

Time limit: 2 sec

Example 1:

Input: L = 1, R = 10
Output: 6
Explanation:
The answer is 6 since 2, 3, 4, 5, 7, 9 are the numbers having prime number of divisors.

Example 2:

Input: L = 2, R = 3
Output: 2

Example 3:

Input: L = 5, R = 5
Output: 1