Chef has recently learned about number bases and is becoming fascinated.
Chef learned that for bases greater than ten, new digit symbols need to be introduced, and that the convention is to use the first few letters of the English alphabet. For example, in base 16, the digits are 0123456789ABCDEF. Chef thought that this is unsustainable; the English alphabet only has 26 letters, so this scheme can only work up to base 36. But this is no problem for Chef, because Chef is very creative and can just invent new digit symbols when she needs them. (Chef is very creative.)
Chef also noticed that in base two, all positive integers start with the digit 1! However, this is the only base where this is true. So naturally, Chef wonders: Given some integer N, how many bases b are there such that the base-b representation of N starts with a 1?

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case consists of one line containing a single integer N (in base ten).

-----Output-----
For each test case, output a single line containing the number of bases b, or INFINITY if there are an infinite number of them.

-----Constraints-----

-----Subtasks-----Subtask #1 (16 points):
- 1 ≤ T ≤ 103
- 0 ≤ N < 103
Subtask #2 (24 points):
- 1 ≤ T ≤ 103
- 0 ≤ N < 106
Subtask #3 (28 points):
- 1 ≤ T ≤ 103
- 0 ≤ N < 1012
Subtask #4 (32 points):
- 1 ≤ T ≤ 105
- 0 ≤ N < 1012

-----Example-----
Input:4
6
9
11
24

Output:4
7
8
14

-----Explanation-----
In the first test case, 6 has a leading digit 1 in bases 2, 4, 5 and 6: 610 = 1102 = 124 = 115 = 106.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from math import sqrt as S \r\nfor _ in range(int(input())):\r\n    n=int(input())\r\n    if n==1:\r\n        print('INFINITY')\r\n        continue \r\n    else:\r\n        ans=0 \r\n        z=int(S(n))\r\n        for i in range(2,z+1):\r\n            temp=n \r\n            while temp:\r\n                r=temp%i \r\n                temp=temp//i \r\n            if r==1: ans+=1\r\n        k=n//2 \r\n        if n>k:\r\n            ans+=n-k \r\n        print(ans)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13065