cho.sh

약수 놀이

시간 제한2초메모리 제한1024 MB

문제

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$