Một số ~M~ được gọi là số huyền bí cơ số ~X~ nếu (M ^ X) > (M & X). Trong đó ^ là phép XOR bit, & là phép AND bit trong C++.

Bạn được cho một mảng ~N~ số nguyên và ~Q~ truy vấn. Mỗi truy vấn được cho bởi bộ ba số ~L, R~ và ~X~.

Yêu cầu: Tìm trong đoạn từ ~L~ đến ~R~ xem có bao nhiêu số huyền bí cơ số ~X~.

Input

• Dòng đầu chứa số nguyên ~N~;

• Dòng tiếp theo chứa ~N~ số nguyên là các phần tử của mảng;

• Dòng thứ ba chứa số nguyên ~Q~ là số truy vấn;

• ~Q~ dòng cuối cùng, mỗi dòng chứa ba số nguyên ~L, R~ và ~X~ biểu thị một truy vấn.

Output

Gồm ~Q~ dòng là kết quả cho từng truy vấn.

Scoring

Sample Input 1

5
1 2 3 4 5
2
1 5 4
2 5 2

Sample Output 1

3
2