# Three Boxes solution codechef

Chef has 33 boxes of sizes AABB, and CC respectively. He puts the boxes in bags of size DD (ABCDA≤B≤C≤D). Find the minimum number of bags Chef needs so that he can put each box in a bag. A bag can contain more than one box if the sum of sizes of boxes in the bag does not exceed the size of the bag.

### Input Format Three Boxes solution codechef

• The first line contains TT denoting the number of test cases. Then the test cases follow.
• Each test case contains four integers AABBCC, and DD on a single line denoting the sizes of the boxes and bags.

### Output Format Three Boxes solution codechef

For each test case, output on a single line the minimum number of bags Chef needs.

### Constraints Three Boxes solution codechef

• 1T1001≤T≤100
• 1ABCD1001≤A≤B≤C≤D≤100

### Subtasks Three Boxes solution codechef

Subtask 1 (100 points): Original constraints

### Sample Input 1  Three Boxes solution codechef

3
2 3 5 10
1 2 3 5
3 3 4 4


### Sample Output 1  Three Boxes solution codechef

1
2
3


## Explanation Three Boxes solution codechef

Test case 11: The sum of sizes of boxes is 2+3+5=102+3+5=10 which is equal to the size of a bag. Hence Chef can put all three boxes in a single bag.

Test case 22: Chef can put boxes of size 11 and 33 in one bag and box of size 22 in another bag.

Test case 33: Chef puts all the boxes in separate bags as there is no way to put more than one box in a single bag.

## Three Boxes solution codechef

There are NN seats in a row. You are given a string SS with length NN; for each valid ii, the ii-th character of SS is ‘0’ if the ii-th seat is empty or ‘1’ if there is someone sitting in that seat.

Two people are friends if they are sitting next to each other. Two friends are always part of the same group of friends. Can you find the total number of groups?

### Input Three Boxes solution codechef

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first and only line of each test case contains a single string SS.

### Output Three Boxes solution codechef

For each test case, print a single line containing one integer ― the number of groups.

• 1T501≤T≤50
• 1N1051≤N≤105

### Subtasks Three Boxes solution codechef

Subtask #1 (100 points): original constraints

### Sample Input 1  Three Boxes solution codechef

4
000
010
101
01011011011110


### Sample Output 1  Three Boxes solution codechef

0
1
2
4


### Explanation Three Boxes solution codechef

Example case 1: Since all seats are empty, the number of groups is 00.

Example case 2: Since only one seat is occupied, the number of groups is 11.

Example case 3: Here, two seats are occupied, but since they are not adjacent, the people sitting on them belong to different groups.

Example case 4: Here, we have 44 groups of friends with size 112222 and 44 respectively. That is, first group is sitting at 22nd seat, second group at 44th and 55th seat, third group at 77th and 88th seat and fourth group at 1010th to 1313th seat.