给定长度为 的序列 。
有 次询问，每次询问给定 ，求出对于 ，存在一个 ，使得 的 的个数。
Mole is hungry again. He found one ant colony, consisting of ants, ordered in a row. Each ant ( ) has a strength .
In order to make his dinner more interesting, Mole organizes a version of
Hunger Games for the ants. He chooses two numbers and ( ) and each pair of ants with indices between and (inclusively) will fight. When two ants and fight, ant gets one battle point only if divides (also, ant gets one battle point only if divides ).
After all fights have been finished, Mole makes the ranking. An ant , with battle points obtained, is going to be freed only if , or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.
In order to choose the best sequence, Mole gives you segments and asks for each of them how many ants is he going to eat if those ants fight.
The first line contains one integer (1≤n≤10^5), the size of the ant colony.
The second line contains integers (1≤s_i≤10^9), the strengths of the ants.
The third line contains one integer (1≤t≤10^5), the number of test cases.
Each of the next lines contains two integers and (1≤l_i≤r_i≤n), describing one query.
Print to the standard output lines. The -th line contains number of ants that Mole eats from the segment .
5 1 3 2 4 2 4 1 5 2 5 3 5 4 5
4 4 1 1
In the first test battle points for each ant are , so ant number is freed. Mole eats the ants .
In the second test case battle points are , so no ant is freed and all of them are eaten by Mole.
In the third test case battle points are , so ants number and are freed. Mole eats only the ant .
In the fourth test case battle points are , so ant number is freed. Mole eats the ant .