Pharaoh Medjed is tired of all his hard work building pyramids. He wants to spice up the game by building some large squares for once. For this, Medjed wants to research how he can best obtain a perfect square amount of bricks to be stacked up into a massive square.

There are ~n~ stonemasons, each with a talent score ~x_i~. When stonemasons are working together, they can produce bricks equal to the product of all of their talent scores, as a team is worth more than the sum of its parts. Medjed wants to build ~q~ squares on different days, but at each day only some range ~[l_i,r_i]~ of the stonemasons are available. For each of these ~q~ ranges, Medjed wants to know how many contiguous subarrays of the available range can produce bricks sufficient for a perfect square number of bricks, i.e. how many subarrays of the given subarray have a perfect square product.

Input

The first line contains two integers ~n\ q~ (~1 \leq n,q \leq 10^5~), the number of stonemasons and the number of days.

The next line contains ~n~ space-separated integers ~x_1\ \dots\ x_n~ (~1 \leq x_i \leq 10^6~), where each ~x_i~ represents the talent score of the ~i~th stonemason.

The next ~q~ lines each contain two integers ~l_i\ r_i~ (~1 \leq l_i \leq r_i \leq n~), the inclusive range of stonemasons that are available on the ~i~th day.

Output

For each of the ~n~ days, output how many arrangements of the available stonemasons can produce a perfect square amount of bricks, i.e. how many subarrays have a perfect square product of talent scores.

Example

Input 1

3 2
1 2 8
1 3
2 3

Output 1

3
1

The only subarrays with perfect square products are ~[1]~, ~[1,2,8]~, ~[2,8]~. So the first day contains all of these, and the second contains only the third one.

Input 2

4 3
2 3 6 12
1 4
2 4
3 3

Output 2

1
0
0

The only counted subarray is ~[2,3,6]~ with product ~36~.

Input 3

5 3
4 9 2 18 8
1 5
3 5
1 2

Output 3

7
2
3