Watch the bits, play your wits;
Count 'em in, Count 'em out,
In a frame of math, it's all you'll see!
Given a string of bits S and an integer k , how many ways are there to reorder the bits and select a subset of this string such that the resulting binary number, when divided by k, will be of the form 2n .
INPUT
The first line has an integer t , the number of test cases.The next t lines has an integer k and a binary number S (a string of 0s and 1s).
OUTPUT
Print t lines - in each line, a single integer that is the maximum possible ways to obtain such a subset such that the value of n is a distinct integer for each subset.
If no such combination is possible, print -1.
CONSTRAINTS
1≤t≤100
1≤k≤30
1≤Length of S≤1000
For the first test case, we consider the subsets [11] and [110].
[11] in decimal form is 3 which is, 3/k=1 and 1=20.
[110] in decimal form is 6 which is, 6/k=2 and 2=21.
Hence there are two possible ways.
For the second test case, the only possible subset is [1], which can't be considered either,
as k=2 doesn't divide the number i.e, the remainder is not zero.