C. Easy Bits

0

0 votes
Bit manipulation, Medium
Problem

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 

1t100

1k30

1Length of S1000

Sample Input
2
3 101
2 1
Sample Output
2
-1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?