Ami là một nhà sáng tạo, mỗi ngày cậu đều tạo ra một dãy số có những quy luật đặc biệt. Và cứ mỗi quy luật đặc biệt tìm được, cậu lại sáng tạo ra được vô số dãy số khác nhau. Hôm nay Ami tìm ra một dãy số G có quy luật rất đơn giản. Nếu dãy số có độ dài là n và Ami chọn một số x bất kì thì tích các phần tử trong dãy G phải đúng bằng x và ước chung lớn nhất của trị tuyệt đối 2 số liên tiếp phải đúng bằng 1. Điều kiện đó có thể được viết lại như sau :

                                      G₁ * G₂ * G₃ * …*G_n = x.

Và

                                      Gcd(|a_i| , |a_i+1|) = 1với mọi i từ 1 đến n – 1.

          Ami cho các bạn độ dài n và số x, các bạn hãy đếm xem có bao nhiêu dãy số khác nhau độ dài n thỏa mãn điều kiện trên nhé. Hai dãy số là khác nhau nếu tồn lại một vị trí i mà tại đó 2 dãy số chứa 2 phần tử khác nhau. Vì kết quả có thể khá lớn nên Ami chỉ cần biết đáp án sau khi đã chia dư cho 10⁹+7 thôi.

Dữ liệu vào

Dòng đầu là số nguyên dương q (q <= 10⁵) là số câu hỏi mà Ami đưa ra.

Tiếp theo là q dòng, mỗi dòng chứa 2 số x và n (x , n <= 10⁶) lần lượt là tích và độ dài dãy số.

Dữ liệu ra

Gồm q dòng là kết quả của câu hỏi tương ứng.