DecenTile Games have launched a new First Person Shooter soldier game, called the Call of War, that young gamers can play on their website. Our protagonist, Ninja (played by you) is a soldier whose mission is to kill all the enemies plotting against you. Your enemies are standing in a circle, numbered clockwise from 1 to n. Initially, the i-th enemy has ai health. You have only one pistol, and infinite bullet magazines. You have to shoot the enemies in order to kill them. Each bullet fired at the enemy decreases their health by 1 (deals 1 damage to it). When the health of some enemy i becomes 0 or less than 0, he dies and his grenade drops down and explodes, dealing bi damage to the next enemy (enemy i+1, if i<n, or enemy 1, if i=n). If the next enemy is already dead, then nothing happens. If the frag from the grenade kills the next enemy, even he drops a grenade, damaging the enemy after him and possibly triggering another explosion, and so on. You have to calculate the minimum number of bullets you need in order to kill all the enemies and win the game.

constraints 1 <= T <= 100 1 <= N <= 10^4 1 <= a, b <= 10^12

sampleinput 1 3 7 15 2 14 5 3 sample output 6 sample input 2 3 11 5 18 18 12 8 5 7 13 5 15 17 8 2 7 18 17 sample output 21 15