Сегодня мы будем решать несколько из 3 задач CodeChef, которые являются частью серии обучения CodeChef DSA.
Проблема
Рассмотрим очень длинное K-значное число N с цифрами d0, d1, …, dK-1 (в десятичной системе счисления; d0 — старшая значащая цифра, dK-1 — младшая значащая цифра). Это число настолько велико, что мы не можем дать его вам на вход в явном виде; вместо этого вам даются только его начальные цифры и способ построения остатка числа.
В частности, вам даны d0 и d1; для каждого i ≥ 2 di представляет собой сумму всех предшествующих (более значащих) цифр по модулю 10 - более формально должна выполняться следующая формула:
Определить, кратно ли N 3.
Формат ввода
Первая строка входных данных содержит единственное целое число T, обозначающее количество тестовых случаев. Ниже приводится описание T тестовых случаев.
Первая и единственная строка каждого набора входных данных содержит три целых числа через пробел K, d0 и d1.
Выходной формат
Для каждого набора входных данных выведите одну строку, содержащую строку «YES» (без кавычек), если число N кратно 3, или «NO» (без кавычек) в противном случае.
Ограничения
- 1 ≤ T ≤ 1000
- 2 ≤ K ≤ 1012
- 1 ≤ d0 ≤ 9
- 0 ≤ d1 ≤ 9
Образец ввода
3 5 3 4 13 8 1 760399384224 5 1
Пример вывода
NO YES YES
Объяснение
Пример 1: Целое число N равно 34748, что не делится на 3, поэтому ответ НЕТ.
Пример 2: Целое число N равно 8198624862486, что делится на 3, поэтому ответ ДА.