As we know you have extra classes at $pmc$ in this beautiful month,so without wasting your time directly going to question.

You are given a positive integer $N$ and $Q$ queries.In each query a positive integer $K$ is given.For each query you have to print number of pairs $(i,j)$ where $1<=i<j<=N$ such that $gcd(i,j)=K$ .

Input

The first line of the input contains two positive integer $N$ and $Q$ space seaparated.

Next $Q$ lines will consist of a single positive integer $K$.

Output

For each query print the required answer in a newline. 

Constrains

$1<=N,Q,K<=500000$