Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Welcome to Criterion Rounds

By Hasinur_ · Limits 1s, 512 MB

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 ≤ 106), the number of queries. Each of the next Q lines will contain a single integer N (1 ≤ N ≤ 105).

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

InputOutput
3
5
6
7
Query 1: 1
Query 2: 0
Query 3: 0

Discussion

Statistics


72% Solution Ratio

EgorKulikovEarliest, Jan '20

MehrajShakilFastest, 0.1s

Brain_LessLightest, 16 MB

mdvirusShortest, 335B

Submit

Login to submit

Editorial

It is easy to prove that for any number n and bases &gt; sqrt(n) there will be no representation whe...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.