Qscqesze is going to hold a blind date party.He takes n boys and m girls into consideration of invitation.Each of them gets a number as a1..an and b1..bm.

The party is in pairs.Everyone is required to choose an opposite sex who is also invited.Every one should be in an only pair.

Qscqesze knows everypair of them if they are willing to come together.

For better result,he wants to ascertain the invitation list to make everyone could gets it's partner.

After his assistant ascertain the invitation list,she writes down the list on a piece of paper.As she is careless,she just writes part of the list down. That is to say Qscqesze gets a piece of paper with incomplete invitation list.

Here comes q questions: how many kinds of paper he might get if all guest in complete list has common divisor gi?

The party is in pairs.Everyone is required to choose an opposite sex who is also invited.Every one should be in an only pair.

Qscqesze knows everypair of them if they are willing to come together.

For better result,he wants to ascertain the invitation list to make everyone could gets it's partner.

After his assistant ascertain the invitation list,she writes down the list on a piece of paper.As she is careless,she just writes part of the list down. That is to say Qscqesze gets a piece of paper with incomplete invitation list.

Here comes q questions: how many kinds of paper he might get if all guest in complete list has common divisor gi?

The first line contains a integer T,indicates the number of testcase.

In each testcase：

The first line contains there integer n m and q,indicates the number of boys ,the number of girls and the number of question.

The next n line contains one 0/1-strings,if the i-th string's j-th character is 1 means the i-th boy is willing to come with the j-th girl and vice versa.

The next line contains n integers, they are ai.

The next line contains m integers, they are bi.

The next line contains q integers,they are gi.

In each testcase：

The first line contains there integer n m and q,indicates the number of boys ,the number of girls and the number of question.

The next n line contains one 0/1-strings,if the i-th string's j-th character is 1 means the i-th boy is willing to come with the j-th girl and vice versa.

The next line contains n integers, they are ai.

The next line contains m integers, they are bi.

The next line contains q integers,they are gi.

提交代码