You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Winter holidays are coming up. They are going to last for n days.

During the holidays, Monocarp wants to try all of these activities exactly once with his friends:

• go skiing;
• watch a movie in a cinema;
• play board games.

Monocarp knows that, on the i-th day, exactly ai friends will join him for skiing, bi friends will join him for a movie and ci friends will join him for board games.

Monocarp also knows that he can't try more than one activity in a single day.

Thus, he asks you to help him choose three distinct days x,y,z in such a way that the total number of friends to join him for the activities (ax+by+cz) is maximized.

Format

Input

The first line contains a single integer t (1≤t≤10e4) — the number of testcases.

The first line of each testcase contains a single integer nn (3≤n≤10e5) — the duration of the winter holidays in days.

The second line contains nn integers a1,a2,…,an(1≤ai≤10e8) — the number of friends that will join Monocarp for skiing on the i-th day.

The third line contains n integers b1,b2,…,bn(1≤bi≤10e8) — the number of friends that will join Monocarp for a movie on the i-th day.

The fourth line contains n integers c1,c2,…,cn(1≤ci≤10e8) — the number of friends that will join Monocarp for board games on the ii-th day.

The sum of n over all testcases doesn't exceed 10e5.

Output

For each testcase, print a single integer — the maximum total number of friends that can join Monocarp for the activities on three distinct days.

Samples

4
3
1 10 1
10 1 1
1 1 10
4
30 20 10 1
30 5 15 20
30 25 10 10
10
5 19 12 3 18 18 6 17 10 13
15 17 19 11 16 3 11 17 17 17
1 17 18 10 15 8 17 3 13 12
10
17 5 4 18 12 4 11 2 16 16
8 4 14 19 3 12 6 7 5 16
3 4 8 11 10 8 10 2 20 3

30
75
55
56

Limitation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output