As their sensei, Kakashi has given a challenge to Naruto and Susuke to test their wits.
It consists of several numbers and it's been asked to find out the number of trailing zeros their product will have. There are n numbers arranged in a row. There are q questions asked. Each question will consist of two integers, l and r, giving the range of indices of numbers of which the answer is to calculated. In other words, given range [l, r], one has to calculate the number of trailing zeros of product of numbers in this range only. Since, Naruto is weak in maths, he has asked for your help.
Input Format--
First line contains n and q, number of integers and number of questions.
Next line will contain n space separated integers.
Each of next q lines will contain l and r, denoting the range.
Note-- Starting index is 1.
Output Format--
Output the answer to each question in separate line.
Constraints--
1≤n,q≤105
1≤ each of the n integers ≤109
1≤l,r≤n
For first question, product is 40.
For second case, product is 12000.