Sau buổi học về số nguyên tố, Muối cảm thấy rất phấn khích khi được biết đến số nguyên tố, nếu có ai hỏi Muối một số nguyên tố thì ngay lập tức Muối có thể trả lời ngay số nguyên tố liền trước và số nguyên tố liền sau. Muối cảm thấy vô địch trong lĩnh vực số nguyên tố nhưng ngày vui ngắn chẳng tày gang, thầy giáo liền cho Muối ~n~ số ~a_i~ và bắt Muối đếm số cách tạo số nguyên tố đặc biệt. Biết rằng số nguyên tố đặc biệt chính là số nguyên tố được tạo nên từ tổng phép XOR tập con bất kì trong những số ~a_i~ thầy giáo cho và tập con đó có ít nhất là ~1~ phần tử. Cảm thấy sự vô địch của mình bị đe dọa, bạn hãy giúp Muối trả lời những câu hỏi của thầy nhé !

Lưu ý: ~2~ cách được gọi là khác nhau khi ~2~ tập con tạo nên số nguyên tố đặc biệt sau khi sắp xếp lại là khác nhau.

Input

• Dòng đầu tiên gồm số ~Q~ ~(1 \leq Q \leq 10)~ là số câu hỏi mà thầy giáo sẽ đặt ra cho Muối
• Ở câu hỏi thứ ~T~ ~(1 \leq T \leq Q)~, dòng thứ nhất cho số ~n~ ~(1 \leq n \leq 10^5)~, dòng thứ hai cho ~n~ số ~a_i~ ~(1 \leq a_i \leq 5000)~

Lưu ý: gọi ~M~ là số lớn nhất trong ~n~ số ~a_i~, ~m~ là số nhỏ nhất trong ~n~ số ~a_i~ thì dữ liệu luôn đảm bảo ~M-m \leq 1000~

Output

• Ứng với ~Q~ câu hỏi, mỗi câu hỏi cho biết số cách tạo số nguyên tố đặc biệt theo định nghĩa của thầy giáo, vì số cách tạo số nguyên tố đặc biệt có thể rất lớn nên đáp án được lấy chia dư cho ~10^9+7~

Sample Input

1
5
3515 3511 3510 3512 3520

Sample Output

5

Sample Input

2
2
3 3
3
3 3 3

Sample Output

1
2

Subtask

• ~50\%~ số test có ~1 \leq n \leq 1000~, ~1 \leq a_i \leq 5000~
• ~50\%~ số test tiếp theo có ~1 \leq n \leq 100000~, ~1 \leq a_i \leq 5000~

Note

Với ~ \oplus ~ là phép XOR đã được đề cập, ta có:

~3511~ là số nguyên tố

~3515 \oplus 3520 \oplus 3510 = 3533~ là số nguyên tố

~3512 \oplus 3515 = 3~ là số nguyên tố

~3515 \oplus 3510 = 13~ là số nguyên tố

~3515 \oplus 3511 \oplus 3510 \oplus 3512 = 2~ là số nguyên tố

~\rightarrow~ Có tổng ~5~ cách tạo nên số nguyên tố đặc biệt