Quest for Messi

In the town of Binaryvile, located in Argentina, there was great anticipation as Lionel Messi, the world champion football player, was scheduled to visit and meet people individually. According to a survey, a large number of people have expressed their interest to meet with Messi one-on-one. However, due to the high number of people, it has become challenging for Messi to meet everyone individually. To ensure fairness, a task has been assigned, and only those who successfully complete it will have the opportunity to meet Messi. As you eagerly await your turn, you understand that solving the task is crucial for meeting your idol. It was an exciting and special opportunity for those who could prove their abilities and have a personal encounter with the famous football star.

You will be given $Q$ queries, for each query you will be given two integer $L$ and $R.$ Your task is to find the sum of the number of ones in the binary representation of each number within the range and determine whether the resulting sum is a prime number or not.

Input

The first line of input data contains a single integer $Q$ — indicating the number of queries.

The only line of the each query contains two integers $L$ and $R$ separated by space — indicating range of numbers.

$1≤Q≤10^6$

$1≤L≤R≤5\times10^6$

Output

Print a single line for each query — “Prime” if the sum of the number of ones in the binary representation of each number within the range is a prime or “Not Prime” otherwise.

Sample

Input	Output
3 1 5 5 10 12 18	Prime Not Prime Prime
Explanation: In the first testcase, $1-001=1$ $2-010=1$ $3-011=2$ $4-100=1$ $5-101=2$ Summation of ones in range is $(1+1+2+1+2=7).$ Now, $7$ is a prime number.