Ray and Evangeline are playing a game named "The Lucky Dice". In this game, each player tosses up an sided special fair dice' alternatively. This continues for turns. In each turn two players both roll the dice once. Then the players add all the numbers they got and the person with the higher sum wins.
A fair dice is a dice that has n sides and each side has the same probability of coming up while tossed up. An sided special fair dice' is a fair dice which has , , , , ..., written on its sides.
They invited you to watch their game. But as it can be boring just to sit there, they want you to take part too. So, As they play you'll try to guess the sum of all dice tosses (you'll guess before the first dice being tossed). You are desperate to win this challenge.
Can you find out what guess will give you the most chance of winning?
Input starts with an integer (), denoting number of test cases.
The next lines contains three integers , , () as described above.
For each test case, print a number in one line containing your answer to that test case.
As the answers can be big, print it modulo . If there are multiple answers, print any of them.
Input | Output |
---|---|
1 6 1 1 | 7 |