There's a line of N numbers where each number is a positive integer that is less than 10⁹. Every second, an alien comes down to the Earth and ask a certain problem. "How many zeros are there after all the other digits when you multiply all the number in range L and R ?". Unfortunately, the alien don't know base 10 numbers. In fact, there're 6 species of alien in the UFO, the first species use base-1 number, second use base-2 and so on. (Yes, the first species do not exist, and therefore will not come down to the Earth).

You are given a task to answer the aliens' questions in their numerical system for a day, which mean there're up to 100,000 questions to be answer.

Input

First line, N <= 100000 which is mentioned above and Q <= 100000 representing number of questions.
Next line, N positive integers on the line on earth, each not exceeding 10⁹.
Next Q lines, 1 <= L <= R <= N representing a range each alien mentioned, and 2 <= S <= 6 representing the alien species.

Output

Q lines, each line is a number represent the answer for each alien.

Example

Input:
5 3
2 3 6 5 100
1 5 2
1 3 6
1 2 3 

Output:
4
2
1