Tetrahedron

Time limit2sMemory limit256 MB

Summary

Given six stick lengths, decide whether they can form the edges of a non-degenerate tetrahedron, where each edge is used once.

Level: Medium4 of 10
Topics: Geometry, Sorting, Math, Greedy
Solved: No attempts yet

Problem

Contrary to the well-known saying "matches are not a toy for children," one boy still loves playing with matches. He does not play pranks with them or start fires, though; he solves various puzzles. For example, he can make the number nine equal the number eleven by moving just one match.

Recently this boy's parents gave him several sets, each consisting of six matches. The boy began building various three-dimensional geometric figures from them. He has already built many figures, but now he is curious: from which sets is it possible to glue the frame of a tetrahedron of nonzero volume using the six matches from the set and glue? Matches cannot be broken, and no match may stick out beyond the frame.

Your task is, given the match lengths for each set, to check whether the frame of a tetrahedron can be glued from them.

Input

The first line contains an integer $n$ ( $1 \le n \le 1000$ ), the number of sets to check. The next $n$ lines each contain six integers in the range from 1 to 1000: the match lengths in the $i$ -th set.

Output

Print $n$ lines, where the $i$ -th line must contain "Yes" if a tetrahedron of nonzero volume can be assembled from the $i$ -th set, or "No" otherwise.

Examples1

Example 1

Input

4
1 1 1 1 1 1
1 2 3 1 2 3
1 2 1 2 1 2
1 2 2 1 2 2

Expected output

Yes
No
Yes
Yes