The coronation of King Berl XXII is soon! The whole royal family, including (n) daughters of Berl XXII, will be present. The King has ordered his jeweler to assemble (n) beautiful necklaces, so each of the princesses could wear exactly one necklace during the ceremony — and now these necklaces are finished. Each necklace consists of (m) gems attached to a gold chain. There are two types of gems used in the necklaces — emeralds and sapphires. So, each necklace can be represented by a sequence of (m) gems (listed from left to right), and each gem is either an emerald or a sapphire. Formally, the (i)-th necklace can be represented by a binary string (s_i) of length (m); if the (j)-th character of (s_i) is 0 , then the (j)-th gem in the (i)-th necklace is an emerald; otherwise, this gem is a sapphire. Now, looking at the necklaces, the King is afraid that some of his daughters may envy the other daughters' necklaces. He wants all necklaces to look similar . Two necklaces are considered similar if there are at least (k) positions where these necklaces contain the same type of gems. For example, if there is a necklace represented by a sequence 01010111 and a necklace represented by a sequence 01100000 , then there are (3) positions where these necklaces contain the same type of gems (both first gems are emeralds, both second gems are sapphires, and both fifth gems are emeralds). So if (k = 3), these necklaces are similar , and if (k = 4), they are not similar . The King thinks that if two of his daughters notice that their necklaces are not similar , then they may have a conflict — and, obviously, he doesn't want any conflicts during the coronation! So Berl XXII wants to tell some of his daughters to wear their necklaces backward. If a necklace is worn backward, then the sequence of gems in this necklace is reversed. For example, if a necklace is represented by a sequence 01100 , then, if worn backward,