An array \(arr\) has indices numbered from 1 to N. You are given Q queries with two integers, \(i X\) in each.

Write a program to find the number of multiples of X in the array \(arr\) that falls between the \(i^{th} index and the end of the array.

Input format

• First line: Two space-separated integers \)N\( and \)Q\(
  
• Second line: \)N\( space-separated integers (denoting the array \)arr\()
  
• Next \)Q\( lines: Two space-separated integers, \)i\( and \)X\(

Output format

For each query, print the number of multiples of \)X\( in the array \)arr\( that falls between the \)i^{th} index and the end of the array.

Constraints

\(1 ≤ N ≤ 10^5\)
\(1 ≤ Q ≤ 10^5\)
\(1 ≤ X ≤ 20000\)
\(1 ≤ arr[i] ≤ 20000\)