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$