Statement

Diana got a package for her birthday and she was very happy because when she opened the box, she found N positive integers in it. However, she likes numbers that are divisible by 3 the most. For each number, she wants to remove some (0 or more) of its digits, so that the number becomes divisible by 3 and still stays positive. If there are multiple ways to achieve this, she wants to get the biggest possible number as the result. The numbers are too big for Diana to handle. Can you help her? For each given number, your program has to determine the greatest positive integer that is divisible by 3, and is obtainable from the given number by deleting 0 or more of its digits. If there is no such number, print -1.