Greedy Pigs

Farmer Park raises 6 pigs. Once each day, he gives them feed.

The pigs eat while sitting around a circular table. Each pig has a good memory: it remembers how much it ate on the previous day, and also how much the two neighboring pigs and the pig sitting opposite it ate on the previous day. Because the pigs are greedy, on the next day each pig wants the sum of those four amounts.

For instance, if pigs 1 through 6 ate 3, 2, 7, 1, 5, and 4 on the first day, then pig 2 wants 17 on the next day: its own previous amount 2 plus the amounts 3, 7, and 5 eaten by its two neighbors and the opposite pig.

Kind Farmer Park wants to satisfy every pig. Each day, N units of fresh feed are delivered to his house. The feed expires after one day, so any leftover feed is discarded.

Given how much the pigs ate on the first day, determine the first day on which Farmer Park can no longer satisfy all 6 pigs.

The input consists of T test cases. The first line contains the integer T.

Each test case has two lines. The first line contains N, the amount of feed delivered each day. The second line contains six integers, separated by spaces, giving the amounts eaten on the first day by pigs 1 through 6 in order.

N is between 1 and 500,000,000, inclusive. Each first-day amount is a natural number no greater than 100.

For each test case, output the first day on which the demands of all 6 pigs cannot be satisfied.