カードの組み合わせ

整数が書いてあるカードが何枚か入っている袋を使ってゲームをしましょう。各回のゲームで参加者はまず、好きな数 n を一つ宣言します。そして、袋の中から適当な枚数だけカードを一度に取り出して、それらのカードに書かれた数の総和が n に等しければ豪華賞品がもらえます。なお、それぞれのゲーム終了後カードは袋に戻されます。

袋の中の m 種類のカードの情報および、g 回のゲームで参加者が宣言した数を入力とし、それぞれのゲームで豪華商品をもらえるカードの組み合わせが何通りあるかを出力するプログラムを作成してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットは以下の形式で与えられます。

m
a1 b1
a2 b2
:
am bm
g
n1
n2
:
ng

１行目にカードの種類数 m （1 ≤ m ≤ 7）、続く m 行に i 種類目のカードに書かれた整数 a_i (1 ≤ a_i ≤ 100) とその枚数 b_i (1 ≤ b_i ≤ 10) が空白区切りで与えられます。

続く行にゲームの回数 g (1 ≤ g ≤ 10)、続く g 行にゲーム i で宣言された整数 n_i (1 ≤ n_i ≤ 1,000) が与えられます。

データセットの数は 100 を超えない。

Output

入力データセットごとに、i 行目にゲーム i で豪華賞品がもらえるカードの組み合わせ数を出力します。

Sample Input

5
1 10
5 3
10 3
25 2
50 2
4
120
500
100
168
7
1 10
3 10
5 10
10 10
25 10
50 10
100 10
3
452
574
787
0

Output for the Sample Input

16
0
12
7
9789
13658
17466