약수 놀이

Bert는 최근 수학 시간에 약수에 대해 배웠다. 임의의 자연수 $x \ge 1$에 대하여

• $D(x)$ : $x$ 의 약수의 개수 (즉, $1$ 이상 $x$ 이하의 자연수 $y$ 중 $x$를 나누어 떨어지게 하는 $y$의 개수)
• $S(x)$ : $x$ 의 약수의 총합 (즉, $1$ 이상 $x$ 이하의 자연수 $y$ 중 $x$를 나누어 떨어지게 하는 $y$의 총합)

이라 정의하자.

예를 들면

• 1의 약수는 $\\{1\\}$ 이므로 $D(1) = 1$, $S(1) = 1$ 이다.
• 10의 약수는 $\\{1, 2, 5, 10\\}$ 이므로 $D(10) = 4$, $S(10) = 18$ 이다.
• 12의 약수는 $\\{1, 2, 3, 4, 6, 12\\}$ 이므로 $D(12) = 6$, $S(12) = 28$ 이다.
• 14의 약수는 $\\{1, 2, 7, 14\\}$ 이므로 $D(14) = 4$, $S(14) = 24$ 이다.
• 15의 약수는 $\\{1, 3, 5, 15\\}$ 이므로 $D(15) = 4$, $S(15) = 24$ 이다.

Bert가 공부하던 모습을 지켜보던 Bert의 누나 Alice는 아래와 같은 퀴즈를 냈보았다: $Q(N, x, A, B, C)$: $1$ 이상 $N$ 이하인 자연수 $y$ 중 아래 세 조건을 모두 만족하는 자연수의 개수는?

1. $|x - y| \le A$
2. $|D(x) - D(y)| \le B$
3. $|S(x) - S(y)| \le C$

예를 들어 $N = 18$ 인 경우를 생각해보자.

• $x = 15, A = 5, B = 2, C = 10$ 인 경우: $y \in \\{10, 12, 13, 14, 15, 16, 17\\}$ 일 때 상기한 세 조건을 모두 만족하므로 답은 7이 된다.
• $x = 15, A = 5, B = 2, C = 20$ 인 경우: $y \in \\{10, 12, 13, 14, 15, 16, 17\\}$ 이외에도 $y \in \\{11, 18\\}$ 일 때 상기한 세 조건을 모두 만족하므로 답은 9가 된다.
• $x = 15, A = 5, B = 1, C = 20$ 인 경우: $y \in \\{10, 14, 15, 16\\}$ 일 때 상기한 세 조건을 모두 만족하므로 답은 4가 된다.

다른 예로 $N = 30$ 인 경우를 생각해보자.

• $x = 14, A = 0, B = 0, C = 0$ 인 경우: $y = 14$ 가 유일하게 조건을 모두 만족시키므로 답은 1이 된다.
• $x = 14, A = 1, B = 0, C = 1$ 인 경우: $y \in \\{14, 15\\}$ 가 조건을 모두 만족시킨다 - 이 퀴즈의 답은 2이다.
• $x = 14, A = 1, B = 1, C = 20$ 인 경우: $y \in \\{14, 15\\}$ 가 조건을 모두 만족시킨다 - 이 퀴즈의 답은 2이다.
• $x = 15, A = 5, B = 2, C = 20$ 인 경우: $y \in \\{10, 11, \dots, 19, 20\\}$ 가 조건을 모두 만족시킨다 - 이 퀴즈의 답은 11 이다.

Alice는 $N$의 값은 고정시켜둔채로 Bert에게 $M$개의 퀴즈를 내고 싶어한다 - 편의상 $i$ 번째 퀴즈는 $(x\_i, A\_i, B\_i, C\_i)$ 네 개의 정수로 표현하자. 입력으로 $N, M$, 그리고 $(x\_i, A\_i, B\_i, C\_i)$ 값들이 주어졌을 때, 각 퀴즈의 정답을 구해보자 (편의상 $i$ 번째 퀴즈의 정답을 $E\_i$ 라 하자).

입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$ 과 $M$ 이 공백으로 구분되어 주어진다. 다음 $M$ 줄에 걸쳐 각 줄에 4개의 정수 $x\_i, A\_i, B\_i, C\_i$가 공백으로 구분되어 주어지는데 이는 $i$ 번째 퀴즈를 표현한다.

각 테스트 케이스의 정답인 $E\_1, E\_2, \dots, E\_M$ 을 공백으로 구분하여 각 줄에 출력한다.

• $1 \le T \le 20$

• $1 \le N \le 200\\,000$

• $1 \le M \le 10\\,000$

• $1 \le i \le M$ 인 $i$에 대하여:

  • $1 \le x\_i \le N$
  • $0 \le A\_i \le N$
  • $0 \le B\_i \le 5$
  • $0 \le C\_i \le 1\\,000\\,000$