EOJ Monthly 2019.7 (based on July Selection)

QQ小方以前不会求最小公倍数，现在他会了，所以他急切的想教会你。

两个或多个整数公有的倍数叫做它们的公倍数，其中除 0 以外最小的一个公倍数就叫做这几个整数的最小公倍数。

我们经常用质因数分解法来求最小公倍数：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。

单单讲给你听肯定是不够的，为了表现自己，QQ小方现在要考考你。

QQ小方决定将问题做再次升级：现在一共有 $n$ 颗星星。星星的闪烁是有规律的。对于第 $i$ 颗星星，它在时刻 $a_i$ 第一次闪烁，之后每隔 $b_i$ 个时刻都会闪烁一次。也就是说，它会在时刻 $a_i,a_i+b_i,a_i+2\times b_i,\cdots$ 闪烁，直到时间的尽头。

QQ小方不禁想到：会不会在某一个时刻，所有星星同时闪烁一次呢？经过简单的分析后，QQ小方发现这种情况几乎不可能发生，于是他决定退而求其次：对于 $l,r$ ，他想知道编号在区间 $[l,r]$ 中的星星会不会在某一时刻同时闪烁一次。QQ小方准备了 $q$ 次询问，要对所有询问都求出答案。