Welcome to Criterion Rounds

The team congratulates you for participating in this contest and for being part of the journey towards excellence. In this very first round of Criterion, we wish you a high rating, success, and prosperity in the future.

Let’s get into the problem now. You will be given some queries. In each query, you have to print F(N) for a positive integer number N.

Definition of F(N) = Number of bases, where representing N (without leading zeros) with a base (1 < base ≤ N) will contain 0 at the second least significant digit and non-zero digit at the least significant digit.

For example: Representing $(13)_{10}$ to binary will give us $(1101)_2$. Here the second least significant digit is 0.

Input

First line of the input will contain a single integer $Q$ ($1 ≤ Q ≤ 10^6$), the number of queries. Each of the next $Q$ lines will contain a single integer $N$ ($1 ≤ N ≤ 10^5$).

Output

For each case print "Query x: y" without quotations where x is the number of the query and y is the required answer.

Sample

Input	Output
3 5 6 7	Query 1: 1 Query 2: 0 Query 3: 0