Вам буде дано 4 числа: \(n, m, a, d\).

Знайти кількість чисел від \(n\) до \(m\) (включно), які не діляться на \(a\), або \(a+d\), або \(a+2d\), або \(a+3d\), або \(a+4d\).

Обмеження

• \(1 \le n \le m \le 2 \times 10^9\)
• \(1 \le a \le 2 \times 10^9\)
• \(1 \le d \le 2 \times 10^9\)
• \(2 \le t \le 100\)

Формат вхідних даних

Перший рядок містить ціле число \(t\) - кількість тестів.

Кожен тест містить 4 числа: \(n, m, a, d\). Числа розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести, в окремих рядках для кожного тесту, відповідь на поставлене завдання

Приклад вхідних даних

3
1 10 2 2
20 100 3 3
100 1000 4 5

Приклад вихідних даних

5
54
543