E. Doodle Jump
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Цель игры Doodle Jump — Главная цель игры — помочь «Дудлеру» (Doodler) взобраться как можно выше по платформам. — Wikipedia.

Это очень популярная игра и xiaodao обожает ее. Однажды она играла в игру и подумала: а есть ли платформа, до которой Дудлер не сможет допрыгнуть ввиду своей низкой прыгучести? Рассмотрим следующую задачу.

Есть n платформ. Высота x-ой (1 ≤ x ≤ n) платформы равняется a·x mod p, где a и p — положительные взаимно простые числа. Максимальная высота прыжка Дудлера равняется h. Иными словами, он может допрыгнуть с высоты h1 до высоты h2 (h1 < h2), если h2 - h1 ≤ h. Вначале Дудлер стоит на земле, где высота равна 0. Вопрос вот в чем: может ли Дудлер добраться до самой высокой платформы?

Например, когда a = 7, n = 4, p = 12, h = 2, высоты платформ равняются 7, 2, 9, 4, как на картинке ниже. Первым прыжком Дудлер может допрыгнуть до платформы на высоте 2, вторым — до платформы на высоте 4, но после этого он не сможет допрыгнуть до платформ повыше. Таким образом, он не может добраться до самой высокой платформы.

Пользователь xiaodao долго думала над этой задачей, но не решила ее. И вот она попросила Вас о помощи. У девушки есть много частных случаев задачи. Ваша задача — решить все частные случаи.

Входные данные

В первой строке записано целое число t (1 ≤ t ≤ 104) — количество частных случаев. В каждой из последующих t строк записано по четыре целых числа a, n, p, h (1 ≤ a ≤ 109, 1 ≤ n < p ≤ 109, 0 ≤ h ≤ 109). Гарантируется, что a и p взаимно просты.

Выходные данные

Для каждого частного случая задачи выведите «YES», если Дудлер может добраться до самой высокой платформы, и «NO» в противном случае.

Примеры
Входные данные
3
7 4 12 2
7 1 9 4
7 4 12 3
Выходные данные
NO
NO
YES