给出一个长度为 nnn 的数列 a1,a2,a3,...,an{ a_1 , a_2 , a_3 , ... , a_n }a1,a2,a3,...,an，以及 mmm 组询问 (li,ri,ki)( l_i , r_i , k_i)(li,ri,ki)，求区间 [li,ri][ l_i , r_i ][li,ri] 中有多少数在该区间中的出现次数与 kik_iki 互质。

第一行，两个正整数 n,mn , mn,m。

第二行，nnn 个正整数 aia_iai 描述这个数列。

接下来 mmm 行，每行三个正整数 li,ri,kil_i , r_i , k_ili,ri,ki，描述一次询问。

输出 mmm 行，即每次询问的答案。

• 1≤n,m≤5×1041\le n,m\le 5\times 10^41≤n,m≤5×104
• 1≤ai≤n1\le a_i\le n1≤ai≤n
• 1≤li≤ri≤n1\le l_i\le r_i\le n1≤li≤ri≤n
• 1≤ki≤n1\le k_i\le n1≤ki≤n