填空题

信服机柜

Question

深信服的设备通常是叠放在机架上的。设备（水平放置）有1U，2U两种高度，2U的高度是1U的两倍。对于一个高度为h的机架，可以叠放多台设备，只要这些设备总高度不超过h就可以。1U、2U两种型号的设备和机架的宽度相等，而且为了避免损坏，必须水平放置设备，而不允许将设备竖直放置。

 

客户买了一批深信服设备，其中1U设备有a台，2U设备有b台。现在他想知道，需要多个高度为h的机架，才能全部放下这批设备？

 

    注：每个机架都可以随意叠放1U和2U的设备，只要总高度不超过h就行，对设备的叠放顺序和数量搭配没有要求。但是不同的叠放策略对于机柜数量的需求是不一样的。比如某客户有2台1U设备和2台2U设备，当使用h=3的机架时，他可以每个机架上放一台1U和一台2U设备，这样总共两个机架就够用了。但如果执意要把两台1U设备叠放在一起，则至少需要3个机架才够用。这里我们假设客户总是按照最好的策略来叠放这些设备。

输入描述： 第一行一个正整数T(T<=100)，表示有T个客户购买了深信服的设备。

接下来T行，每行三个整数a，b，h。(0<=a,b<=100000，2<=h<=100000)

表示这个客户1U设备有a台，2U设备有b台，他所用的机架高度为h。输入样例： 2 2 2 3 0 10 5 输出描述： 输出T行，每行一个正整数，表示该客户最少需要的机架数量。输出样例 2 5