Daisy and her two friends, Fitz and Simmons recently got addicted to the new game-Acquire the Cirangles.

A K-Cirangle is defined as a triangle made of circles, with K rows, numbered from 1 to K. For each row 'i' between 1 and K, there are 'i' circles in that row.

For example, A 4-Cirangle would look like the following:

The game is as follows:

1. The players play as a team. Each of the three players-Daisy, Fitz and Simmons are given some points initially. Let's call them- D, F and S for simplicity.
2. Each circle in a Cirangle can be acquired by any of the three players. When a circle is acquired by a player, his/her points are reduced by 1.
3. Same player can't acquire two adjacent circles of a Cirangle.
4. A Cirangle is called to be stable if it can be completely acquired by the team.
5. An example of a stable Cirangle is :

Here D, F and S represent circles acquired by Daisy, Fitz and Simmons respectively.

Assuming that there are infinitely many K-Cirangles available for the team, and Given the values of D,F,S and K- find the maximum number of K-Cirangles that can be made stable, using the given initial points.

Input Format:
First line contains T, the number of test cases. T lines follow.
Each line consists of 4 space separated number denoting D,F,S and K.

Output Format:
For each test case, print the answer, the maximum number of K-Cirangles that can be made stable.

Constraints:
1 ≤ T ≤ 250
0 ≤ D,F,S ≤ 10¹⁸
1 ≤ K ≤ 10⁹

Note: Please note that you don't need to make the cirangles stable using the same pattern. They can be made stable using different patterns.
Hint: Binary Search