Бесконечное дерево
Во время полета к планетарному системе Link-Cut, вам стало скучно, и Люси начала рассказывать вам о ядерной физике. Конкретно, о том, как работают цепные реакции в реакторе вашего корабля.
Поскольку корабль необычен, то и реактор тоже необычен; он генерирует уникальные атомы, каждый с уникальной характеристикой, то есть с положительным целым числом. При генерации нового атома выбирается наименьшее доступное значение характеристики (вы также можете думать об этом как о числе, на единицу большем, чем количество атомов, существовавших ранее). Изначально реактор производит атом (с номером 1), после чего начинается фаза расщепления.
Атомы, в порядке их характеристик, начинают создавать дополнительные атомы. Атом с характеристикой создаст дополнительных атомов. Здесь означает количество установленных битов в двоичном представлении , формально это можно определить следующим образом:
где - наибольшее неотрицательное целое такое, что делится на .
Эти операции формируют дерево цепной реакции. Однако такая конструкция не очень устойчива, поэтому разрывы происходят часто. Каждый разрыв можно определить двумя атомами (конкретно, их характеристиками), и во время каждого разрыва все соединения на пути между этими двумя атомами разрушаются. Задача реактора - восстановить их, что является довольно сложным процессом, поэтому мы сосредоточимся на одной из его самых простых частей, то есть на вычислении требуемой энергии, которая равна количеству разрушенных соединений.
Часть этого дерева
В этот момент ваш корабль был атакован астероидом, и Люси поспешила починить ущерб, дав вам задание написать программу для вычисления энергии. Поскольку вы все еще учитесь, она упростила задачу, утверждая, что разрывы будут происходить только между атомами, чьи характеристики меньше .
Приближается крайний срок, поэтому не затягивайте и выполняйте свое задание.
Входные данные
Первая строка содержит два целых числа и - наибольшее значение характеристики в каждом разрыве и количество разрывов.
Каждая из следующих строк содержит два целых числа и - значение характеристики двух атомов, между которыми происходит разрыв. Обратите внимание, что каждый запрос независим от других.
Выходные данные
Для каждого разрыва выведите количество разрушенных соединений.
Примеры
Оценивание
( points): ;
( points): ;
( points): ;
( points): Без дополнительних ограничений;