Range Prod GCD

長さがの数列が与えられます．この数列に対して個のクエリが与えられるので，順に処理してください．

番目（）のクエリでは，（ かつ ）が与えられるので， と の最大公約数をで割った余りを出力する．

ただし， とは のことである．

• 各クエリにおいて かつ
• 入力はすべて整数

各クエリにおいて， と の最大公約数をで割った余りを出力．

10 5
39 49 9 22 28 5 23 40 26 14
1 3 7 10
3 7 4 6
5 8 3 5
8 8 3 3
2 2 2 2

91
3080
56
1
49

• クエリ
  と の最大公約数は です．
• クエリ
  と の最大公約数は です．
• クエリ
  と の最大公約数は です．
• クエリ
  と の最大公約数は です．
• クエリ
  と の最大公約数は です．