약수 놀이

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가 공부하는 모습을 지켜보던 누나 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 \{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)$가 주어졌을 때, 각 퀴즈의 답 $E_i$를 구하여라.

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

각 테스트 케이스의 첫 줄에는 공백으로 구분된 $N$과 $M$이 주어진다. 이어서 $M$개의 줄에 걸쳐 공백으로 구분된 네 정수 $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$