#!/usr/bin/env python3 # from typing import * import sys import io import math import collections import decimal import itertools import bisect import heapq def input(): return sys.stdin.readline()[:-1] # sys.setrecursionlimit(1000000) # _INPUT = """3 # """ # sys.stdin = io.StringIO(_INPUT) def f(N): if N == 0: return 0 N1 = N d = 0 while N1 > 1: N1 >>= 1 d += 1 if N % 2 == 0: return (1<