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.
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).
For each case print "Query x: y" without quotations where x is the number of the query and y is the required answer.
3 5 6 7
Query 1: 1 Query 2: 0 Query 3: 0
Login to submit
It is easy to prove that for any number n and bases > sqrt(n) there will be no representation whe...