2.2 Devansh Anna And his Idlis
Devansh Anna was arranging the idlis at his stall near the college, as he did every morning. The sun was just beginning to rise, and students were slowly trickling in for breakfast. Some of the idlis already had chutney spread on them, while others were plain, waiting for the right amount of sauce.
Devansh Anna liked to keep things interesting. While arranging the row, he noticed patterns in the way the idlis were placed and got a curious idea. He decided to play a little mental experiment with the row.
He looked carefully at the line of idlis, observing which ones had chutney and which didn’t. Then, for each idli in the row, he imagined changing just that one: if it had chutney, he would remove it; if it didn’t, he would add chutney. He repeated this thought for every single idli, mentally creating a new version of the row each time.
After finishing the exercise, he imagined all the “versions” of the row, lined up one below the other, like a small matrix of possibilities.Devansh Anna smiled to himself, thinking about how interesting it would be to know the total number of idlis with chutney across all these versions.
Now Devansh Anna is wondering - can you help him figure out how many idlis have chutney in total across all the versions?
Constraints
t (1 <= t <= 1000)
n (1 <= n <= 10)
Input Format
First line: integer t (1 <= t <= 1000) - number of rows Anna is checking.
For each row:
Line 1: integer n (1 <= n <= 10) - number of idlis in the row.
Line 2: string of length n - each character represents an idli: 1 for idli with chutney, 0 for idli without.
Output Format
For each row, print a single integer - the total number of idlis with chutney across all versions.
Example 1
Input:
1
3
101
Output:
5
Explanation:
s = 101 → versions: 001, 111, 100 → total chutney = 5
Log In to solve the Question