Count triplets in a sorted doubly linked list whose sum is equal to a given value x

You are given a sorted doubly linked list of distinct nodes that means no two nodes present in the list have the same data. You are also given an integer 'X'.Your task is to count the number of triplets in the list that sum up to a given value 'X'.

A doubly linked List (DLL) contains an extra pointer, called the previous pointer, together with the next pointer and data, which are there in the singly linked list such that both forward and backward navigation is possible.

For example, DLL is 1<->2<->3<->4 NULL and the given integer 'X' is 9, then the number of triplets having the sum 9 is only one, and that is (2,3,4).

Note:

1. If no such triplets exist, return zero.
2. At least three elements will always be present in the linked list.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains space-separated integers denoting the nodes of the linked list. Each line is guaranteed to have -1 at the end to signify the end of the linked list.

The second line of each test case contains a single integer 'X' denoting the value of triplet sum.

Output format :

For each test case, print an integer denoting the count of the triplets.

The output of every test case will be printed in a separate line. 

Note:

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 10
3 <= 'N' <= 100
1 <= 'X' <= 10^8
1 <= 'V' <= 10^8

Where 'V' denotes any linked list element.

Time Limit: 1 sec