Vasya studies divisibility rules at school. Here are some of them: Divisibility by 2 . A number is divisible by 2 if and only if its last digit is divisible by 2 or in other words, is even. Divisibility by 3 . A number is divisible by 3 if and only if the sum of its digits is divisible by 3 . Divisibility by 4 . A number is divisible by 4 if and only if its last two digits form a number that is divisible by 4 . Divisibility by 5 . A number is divisible by 5 if and only if its last digit equals 5 or 0 . Divisibility by 6 . A number is divisible by 6 if and only if it is divisible by 2 and 3 simultaneously (that is, if the last digit is even and the sum of all digits is divisible by 3 ). Divisibility by 7 . Vasya doesn't know such divisibility rule. Divisibility by 8 . A number is divisible by 8 if and only if its last three digits form a number that is divisible by 8 . Divisibility by 9 . A number is divisible by 9 if and only if the sum of its digits is divisible by 9 . Divisibility by 10 . A number is divisible by 10 if and only if its last digit is a zero. Divisibility by 11 . A number is divisible by 11 if and only if the sum of digits on its odd positions either equals to the sum of digits on the even positions, or they differ in a number that is divisible by 11 . 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 10 it is enough to check fulfiling 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 rule is called the 11 -type rule (it works for number 11 ). In some c