A. Gift Carpet

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently, Tema and Vika celebrated Family Day. Their friend Arina gave them a carpet, which can be represented as an n⋅m�⋅� table of lowercase Latin letters.

Vika hasn't seen the gift yet, but Tema knows what kind of carpets she likes. Vika will like the carpet if she can read her name on. She reads column by column from left to right and chooses one or zero letters from current column.

Formally, the girl will like the carpet if it is possible to select four distinct columns in order from left to right such that the first column contains "v", the second one contains "i", the third one contains "k", and the fourth one contains "a".

Help Tema understand in advance whether Vika will like Arina's gift.

Input

Each test consists of multiple test cases. The first line of input contains a single integer t� (1≤t≤1001≤�≤100) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers n�, m� (1≤n,m≤201≤�,�≤20) — the sizes of the carpet.

The next n� lines contain m� lowercase Latin letters each, describing the given carpet.

Output

For each set of input data, output "YES" if Vika will like the carpet, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

Example

input

Copy

5

1 4

vika

3 3

bad

car

pet

4 4

vvvv

iiii

kkkk

aaaa

4 4

vkak

iiai

avvk

viaa

4 7

vbickda

vbickda

vbickda

vbickda

output

Copy

YES
NO
YES
NO
YES

Note

In the first sample, Vika can read her name from left to right.

In the second sample, Vika cannot read the character "v", so she will not like the carpet.

解题说明：此题是一道字符串题，直接遍历，判断列中是否存在对应的字母。

#include <stdio.h>
int main() 
{int t;scanf("%d", &t);while (t--){int n, m;scanf("%d %d ", &n, &m);char str[20][20];char name[5] = "vika";int i, j;int b = 0, c = 0;for (i = 0; i < n; i++){for (j = 0; j < m; j++) {scanf(" %c", &str[i][j]);}}j = 0;for (j = 0; j < m; j++){for (i = 0; i < n; i++){if (str[i][j] == name[b]){b++;c++;break;}}}if (c == 4) {printf("yes\n");}else{printf("no\n");}}return 0;
}