Ильнур – большой любитель кофе. В офисе, где он работает, есть q кофейных автоматов. Цены на кофе в разных кофе-автоматах отличаются, причём каждый из них принимает и выдаёт сдачу купюрами только двух номиналов — ai и bi тугриков (1 6 i 6 q). Перед посещением i-го кофеавтомата Ильнур берёт с собой банкноты достоинством ai и bi тугриков и пытается расплатиться ими за кофе стоимостью ci тугриков. Однако ему это не всегда удаётся. Например, если кофейный автомат принимает и выдаёт сдачу только купю

Шаги решения задачи:

1. Рассмотрим каждый кофе-автомат отдельно. Посчитаем, сколько раз Ильнур сможет расплатиться имеющимися у него банкнотами в каждом автомате.

2. Для каждого автомата проверим, будет ли оставшаяся сумма после оплаты кофе кратной ai или bi (или обеим). Если да, то Ильнур сможет получить сдачу и закупиться кофе. Если нет, то он не сможет расплатиться имеющимися у него банкнотами.

3. Посчитаем общее количество автоматов, в которых Ильнур сможет расплатиться. Это и будет ответом на задачу.

Объяснение решения:

Ильнур имеет ai и bi тугриков купюрами и хочет расплатиться ими за кофе стоимостью ci тугриков. Имея ai и bi тугриков, Ильнур может заплатить за кофе только теми номinaлами, которые принимает автомат. Поэтому для каждого автомата (i-го) нужно выяснить, можно ли расплатиться имеющимися у Ильнура купюрами.

Для этого нужно проверить следующие условия:
– Если оставшаяся сумма после оплаты кофе (ci – ai) кратна ai, то Ильнур сможет получить сдачу имеющимися у него купюрами. Это происходит в случае, если кофе стоит целое число раз больше ai. То есть (ci – ai) % ai = 0.
– Аналогично, если оставшаяся сумма после оплаты кофе (ci – bi) кратна bi, то Ильнур сможет получить сдачу имеющимися у него купюрами. Это происходит в случае, если кофе стоит целое число раз больше bi. То есть (ci – bi) % bi = 0.

Если выполнено хотя бы одно из этих условий, то Ильнур сможет расплатиться имеющимися у него купюрами и получить сдачу.

После проверки всех автоматов, мы будем знать, в каких автоматах Ильнур может расплатиться. Общее количество таких автоматов и будет ответом на задачу.