SOLVE

LATER

EEDC Lab

/

You must be tired using the Function Generator and the CRO during the EEDC Lab. But the Midsem Lab Test is yet to come. You have to prepare for it and perform all the experiments in order to know the working of those machines.

You decide to go to the lab and try those experiments but the lab is locked. The key is with the CC3 guard and he will give you the key only if you answer his queries.

The guard loves the numbers divisible by *2*,*3* and *5*.

Lucky indices are those index for which the sum of numbers formed using the array elements on its left and array elements on its right is divisible by2,3and5.For example:- Consider the array \([1,2,3,4,5]\) and index

3(1- based). The number formed using the array elements on the left is \(12\) and the number formed using the array elements on the right is \(45\).

So he gives you an array of integers and asks you *Q* queries.
In each query he provides you two integers *L* and *R*. You have to answer how many lucky indices are there between *L* to *R* (both inclusive).

See sample for more clarity.

**Input Format:**

First line contains an integer *N*, which denotes the length of the array *A*.

Second line contains *N* space-separated integers.

Next line contains number of queries *Q*.

Next *Q* lines contain two integers *L* and *R*.

** Output Format **

For each query, print the number of lucky indices present in that range.

** Constraints **

*1* ≤ \(N,Q\) ≤ \(10\)^{6}

\(0 ≤ A[i] ≤ 9\)

\(1 ≤ L ≤ R ≤ N\)

Problem Setter - Harsh Jain

Explanation

For

** Index 1: ** Left Number: *0* and Right Number: \(575675\)

** Index 2: ** Left Number: *1* and Right Number: \(75675\)

** Index 3: ** Left Number: \(15\) and Right Number: \(5675\)

** Index 4: ** Left Number: \(157\) and Right Number: \(675\)

** Index 5: ** Left Number: \(1575\) and Right Number: \(75\)

** Index 6: ** Left Number: \(15756\) and Right Number: *5*

** Index 7: ** Left Number: \(157567\) and Right Number: *0*

Only sum of numbers at index 5 is divisible by 2,3 and 5.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...