根据哥德巴赫猜想（每个不小于 6 的偶数都可以表示为两个奇素数之和），定义

哥德巴赫矩阵 A 如下：对于正整数对(i,j)，若 i+j 为偶数且 i,j 均为奇素数，则A_i,j = 1，

否则A_i,j = 0。现在有若干询问(x1,y1,x2,y2)，你需要回答下列式子的值

第一行一个整数 m

m 行，每行一个整数，表示对应询问的答案

30%的数据保证 x2, y2, m ≤ 100

100%的数据保证 1 ≤ x1 ≤ x2 ≤ 10⁶; 1 ≤ y1 ≤ y2 ≤ 10⁶; m ≤ 1000