Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Counting Arrays

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given two positive integer numbers *x* and *y*. An array *F* is called an *y*-factorization of *x* iff the following conditions are met:

- There are
*y*elements in*F*, and all of them are integer numbers; - .

You have to count the number of pairwise distinct arrays that are *y*-factorizations of *x*. Two arrays *A* and *B* are considered different iff there exists at least one index *i* (1 ≤ *i* ≤ *y*) such that *A*_{i} ≠ *B*_{i}. Since the answer can be very large, print it modulo 10^{9} + 7.

Input

The first line contains one integer *q* (1 ≤ *q* ≤ 10^{5}) — the number of testcases to solve.

Then *q* lines follow, each containing two integers *x*_{i} and *y*_{i} (1 ≤ *x*_{i}, *y*_{i} ≤ 10^{6}). Each of these lines represents a testcase.

Output

Print *q* integers. *i*-th integer has to be equal to the number of *y*_{i}-factorizations of *x*_{i} modulo 10^{9} + 7.

Example

Input

2

6 3

4 2

Output

36

6

Note

In the second testcase of the example there are six *y*-factorizations:

- { - 4, - 1};
- { - 2, - 2};
- { - 1, - 4};
- {1, 4};
- {2, 2};
- {4, 1}.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2017 03:28:13 (c6).

Desktop version, switch to mobile version.

User lists

Name |
---|