Это простая версия задачи. Различия между двумя версиями выделены жирным шрифтом. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
У Shohag есть два целых числа \(x\) и \(m\). Помогите ему подсчитать количество целых чисел \(1 \le y \le m\) таких, что \(\mathbf{x \neq y}\) и \(x \oplus y\) является делителем\(^{\text{∗}}\) либо \(x\), либо \(y\), либо сразу обоих чисел. Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
\(^{\text{∗}}\)Число \(b\) является делителем числа \(a\), если существует целое число \(c\) такое, что \(a = b \cdot c\).
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая и единственная строка каждого набора входных данных содержит два целых числа \(x\) и \(m\) (\(1 \le x \le 10^6\), \(1 \le m \le 10^{18}\)).
Гарантируется, что сумма \(x\) по всем наборам входных данных не превосходит \(10^7\).
Для каждого набора входных данных выведите одно целое число — количество подходящих \(y\).
В первом наборе входных данных, для \(x = 6\) существует \(3\) допустимых значения для \(y\) среди целых чисел от \(1\) до \(m = 9\) — числа \(4\), \(5\) и \(7\).
Во втором наборе входных данных для \(x = 5\) существует \(2\) допустимых значения для \(y\) среди целых чисел от \(1\) до \(m = 7\) — числа \(4\) и \(6\).
5 6 9 5 7 2 3 6 4 4 1
3 2 1 1 0
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач