Вася проходит в школе признаки делимости. Вот некоторые из них:

• Признак делимости на 2. Число делится на 2 тогда и только тогда, когда его последняя цифра делится на 2, то есть является четной.
• Признак делимости на 3. Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.
• Признак делимости на 4. Число делится на 4 тогда и только тогда, когда две его последние цифры составляют число, которое делится на 4.
• Признак делимости на 5. Число делится на 5 тогда и только тогда, когда последняя его цифра равна 5 или 0.
• Признак делимости на 6. Число делится на 6 тогда и только тогда, когда оно делится одновременно на 2 и на 3 (то есть если последняя цифра четная и сумма цифр делится на 3).
• Признак делимости на 7. Такой признак делимости Васе не известен.
• Признак делимости на 8. Число делится на 8 тогда и только тогда, когда число, образованное тремя его последними цифрами, делится на 8.
• Признак делимости на 9. Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.
• Признак делимости на 10. Число делится на 10 тогда и только тогда, когда оно оканчивается на ноль.
• Признак делимости на 11. На 11 делятся только те и только те числа, у которых сумма цифр на нечетных позициях либо равна сумме цифр на четных позициях, либо отличается от неё на число, делящееся на 11.

Васю заинтересовал тот факт, что некоторые признаки делимости похожи друг на друга. Действительно, для проверки делимости числа на 2, 4, 5, 8 и 10 достаточно проверить выполнение некоторого условия для одной или нескольких последних цифр. Такие признаки Вася называет признаками 2-типа.

Если для проверки делимости нужно найти сумму цифр и проверить, делится ли она на заданное число, то Вася называет такой признак признаком 3-типа (потому что он работает для чисел 3 и 9).

Если нужно найти разность суммы цифр на нечетных позициях и суммы цифр на четных позициях и проверить, делится ли она на заданный делитель, такой признак называется признаком 11-типа (он подходит для числа 11).

В некоторых случаях нужно раскладывать делитель на несколько множителей и проверять выполнение признаков разных типов (2-типа, 3-типа или 11-типа). Например, для числа 6 мы проверяем признаки 2-типа и 3-типа, для числа 66 — всех трех типов. Такие комбинированные признаки делимости называются признаками 6-типа.

И, наконец, есть некоторые числа, для которых не подходят признаки ни 2-типа, ни 3-типа, ни 11-типа, ни 6-типа. Наименьшим таким числом является число 7, поэтому будем говорить, что для них выполняются признаки таинственного 7-типа, пока нераскрытого Васей.

Васина мечта — получить признаки делимости на все возможные числа. Он не намерен ограничиваться десятичной системой счисления. Поскольку чисел очень много, сам он не справится. Вася попросил вас написать программу, определяющую тип признака делимости в системе счисления с основанием b для заданного делителя d.