最近，蚂蚁王国举办了一场勇士选拔赛，以此来选拔出王国的勇士。
现在有 n 只蚂蚁报名，蚂蚁编号分别为 1,2,.......,n，其中第 i 只蚂蚁有一个特性值为 a_i。
勇士选拔赛一共安排了 q 场比赛，每场比赛开始前每只蚂蚁的得分都是 0 分，其中第 i 场比赛由编号为 [l_i, r_i] 的蚂蚁参加。每一只编号在 [l_i, r_i] 蚂蚁都会在这一轮比赛中与其他所有参赛的蚂蚁进行比较。
具体地说，在第 i 轮比赛中，对于编号为 x,y 的两只蚂蚁，如果 x,y\in[l_i,r_i]（其中 \in 表示属于，即 x, y 在 l_i \sim r_i 之间 ） ，并且他们的特征值满足 a_x|a_y （a_x 整除 a_y，即 a_y 除以 a_x 余数为 0），那么编号为 x 的这只蚂蚁将在这个比较中获得 1 分，对于所有满足条件的 x,y 都会在这一轮比赛中进行比较。
注意，每一轮比赛开始前，所有蚂蚁的得分都为 0，并且对于第 i 轮比赛，编号为 x \in [l_i,r_i] 的蚂蚁会和所有其他编号满足参赛要求的蚂蚁进行比较。
蚂蚁国王想知道每场比赛中，有多少只蚂蚁的得分 v 没有满足 v=r_i - l_i 。