Given an integer $n$. There $q$ queries, each of the form $(l, r)$, count the number of integers in range $[l, r]$ that are coprime to $n$ (.i.e $GCD(n, x)=1$).
### Input
- The first line contains 2 integers $n, q$.
- The next $q$ lines, each line contains 2 integers $l, r$, a query.
### Output
- Print $q$ integers, the answers for $q$ queries.
### Constraints
- $1 \le n, l, r \le 10^{12}$.
- $1 \le q \le 10^4$.
### Example
Input:
```
10 2
1 5
5 10
```
Output:
```
2
2
```
