Background

Description

Q国和T国将要开战，有n个仁人志士（自由人）将要加入自己期待的国家，辅助自己选中的国家获得胜利，每个自由人有着自己最初的选择。你是T国的腹黑军师，你可以用嘴遁说服一个自由人加入与其预期相反的国家，当这些自由人分别加入你想要的国家后，T国将会最大可能获得战争的胜利（也就是把坑货都甩给Q国）。但是由于这些自由人间有着极其错综复杂的敌对关系，当一个自由人加入其相反的国家后，与其敌对的自由人将会也加入与自己预期相反的国家。为了自身的安全，对任意一个自由人，你仅可以进行一次嘴遁。那么有多少种办法使这些自由人根据你的计划加入国家。（不计使用嘴遁的顺序）。

Format

Input

输入第一行有一个数K，表示以下有1<K<=1000组测试数据。
每组测试数据的格式如下：
第一行 一个数N（0 < N <= 50）
第二行 N个0或者1的数，表示开始时N个自由人预期加入的国家。（0代表T国，1代表Q国）
第三行 N个0或者1的数，表示你计划中所有人加入的国家。
接下来 每行两个数I J，表示第 j个自由人对第i个有敌对关系（这是单向的，也就是当第i个人加入相反的国家后第j个人也会加入相反的国家）。每组数据以 0 0 结束。

Output

如果有可行方法，输出总数，否则输出“Oh,it's impossible~!!” 不包括引号

Sample 1

Input

2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0

Output

4
Oh,it's impossible~!!

Limitation

Hint

第一组数据的说明：
一共以下四种方法：
说服自由人1
说服自由人2
说服自由人3
说服自由人1、2、3 （全部说服，不记顺序）

Source