Hard Divide and Conquer > Dynamic Programming

Pokemon found a binary number. He can switch places of its bits. Help him make the greatest binary number without leading zeros which is divisible by 30 by switching bits position. If it is not possible then return -1. Input: ------ Input starts with an integer **T (1<=10)**, denoting the number of test cases. Each case contains a binary number. Length of the binary number is less then **1000**. You can assume there are no leading zeros. Output: ------- For each case of input, output the greatest binary number which is divisible by 30 otherwise print -1. Sample Input ------------ 2 10 11101 Sample Output ------------- -1 11110

Rezwanul Islam Maruf