Cá Nóc và Thợ Săn là hai người bạn rất thân với nhau, nhưng mà họ lại rất thích tranh giành với nhau từ đồ chơi, đồ ăn đến các danh hiệu và giải thưởng. Hôm nay là một ngày đẹp trời, một người bạn thân khác của cả Cá Nóc và Thợ Săn là Milo đã mời cả hai người đến nhà chơi và tặng cho hai người một dãy số ~COV~ gồm ~N~ số nguyên dương. Để cho hai người không tranh giành nhau, Milo quyết định chia dãy ~COV~ thành hai tập con ~I~ và ~D~ sao cho ~\gcd(\prod I, \prod D) = 1~ (~\prod X~ là tích của tất cả các số trong tập ~X~). Việc chia dãy ~COV~ thành hai tập con thỏa mãn điều kiện có vẻ rất đơn giản đối với Milo. Tuy nhiên để thử thách bản thân mình, Milo đã tính thử xem liệu có bao nhiêu cách chia dãy số ~COV~ thành đúng hai tập ~I~ và ~D~ khác rỗng sao cho thỏa mãn điều kiện trên. Việc pha trà đón Cá Nóc và Thợ Săn đến chơi khá là khó khăn và tốn nhiều thời gian của Milo nên Milo muốn nhờ các bạn tính xem có bao nhiêu cách chia dãy số ~COV~ thỏa mãn. Bởi vì kết quả có thể rất lớn nên Milo chỉ muốn biết phần dư của nó khi chia cho ~10^9 + 7~.

Dữ liệu

• Dòng đầu tiên chứa số lượng trường hợp ~T~ mà Milo xem xét đến.

• Dòng đầu tiên của mỗi trường hợp chứa số nguyên dương ~N~ là số lượng phần tử trong dãy ~COV~ .

• Dòng thứ hai của mỗi trường hợp chứa ~N~ số nguyên dương miêu tả dãy số ~COV~ .

Kết quả

• Ghi kết quả ra ~T~ dòng, mỗi dòng là kết quả cần tìm trong từng trường hợp.

Giới hạn

• ~1 \le T \le 5~

• ~1 \le N \le 10^5~

• ~1 \le COV_i \le 10^6~

Chấm điểm

• 20% số điểm có ~1 \le N, COV_i \le 15~,

• 30% số điểm tiếp theo có ~1 \le N \le 10^3~

• 50% số điểm còn lại có ~1 \le N \le 10^5~

Ví dụ

Sample Input

3
3
2 3 6
3
2 3 1
4
2 3 6 1

Sample Output

0
6
2