Vasya got interested by the fact that some divisibility rules resemble each other. In fact, to check a number's divisibility by 2, 4, 5, 8 and 10it is enough to check fulfilling some condition for one or several last digits. Vasya calls such rules the 2-type rules. If checking divisibility means finding a sum of digits and checking whether the sum is divisible by the given number, then Vasya calls this rule the 3-type rule (because it works for numbers 3 and 9). If we need to find the difference between the sum of digits on odd and even positions and check whether the difference is divisible by the given divisor, this ru