Three Sum Target

Given an array of integers (A) and a target integer (T), determine whether there exist three distinct elements (a, b, c) in (A) such that (a + b + c = T). For each test case, output YES if such a triplet exists; otherwise, output NO.

The input starts with an integer representing the number of test cases. Each test case is given in one line: the first integer denotes (n), the number of elements in the array, followed by (n) integers (the elements of (A)) and ending with the target integer (T).

inputFormat

Input is read from standard input (stdin).

The first line contains an integer (T), the number of test cases. Each of the following (T) lines represents a test case containing (n+2) space-separated integers: the first integer is (n) (number of array elements), the next (n) integers describe the array (A), and the last integer is the target sum (T).

outputFormat

For each test case, print a single line to standard output (stdout) containing YES if there exists a triplet in the array that sums to the target, otherwise print NO.## sample

2
5 1 2 3 4 5 9
4 1 2 3 4 10

YES
NO