To drop out or not to drop out!

Time Limit: 10 Seconds    Memory Limit: 65536 KB

Shahin's studying at a university that has many buildings and they're quite far from each other. At least Shahin thinks so. There are a number of roads between some buildings in a way that you can travel between any two buildings directly or indirectly and you can only travel between buildings via these roads (no bus, no car, walk only! And nobody knows for sure how many buildings and roads there are). 

So Shahin's having bad days at university and to make things even worse he recently received an anonymous email that says university has B buildings and R roads. This email also contains shortest distance between each university building. The numbers are so big he decides that's it, he's tired of walkings so much and he should drop out of this tiresome university! 

Since this email could be a prank by his friends he decides to verify these numbers and see if they can really be shortest distance between university buildings (his friends aren't cruel so if this email is a prank the numbers can't possibly be shortest distance between B buildings via R roads). 

As the cliché goes this task is brought to you and you're the only one in the world capable of solving it. 

Input

In the first line of input there is T, number of test-cases. 

Each test case starts with a line containing B ≤ 200 and R. 

Then B₁ line follows describing distances between buildings. The i^th line contains Bi numbers and the j^th number in i^th line is the distance between buildings i and i+j. 

Output

For each test case output a single line. “YES” if the numbers in email are valid or “NO” if email is a prank. 

Sample Input

2
3 3
1 2
2
3 2
1 2
2

Sample Output

YES
NO

Submit

Source: 13th Iran Nationwide Internet Contest - Isfahan