29015번 - Детали 다국어

문제

После победы в очередной гонке, Молния Маккуин решил обновить покрышки и другие свои детали. Придя в магазин, Молния был обескуражен количеством различных товаров. Радостный, он бросился набирать себе в багажник всякие железные штучки. Но в один момент что-то начало тревожить гоночную машину. Это чувство тревоги не покидало Молнию пока, стоя в очереди в кассу, он не осознал, что забыл все свои гаечки дома. А без гаечек невозможно совершить покупку, ведь это главная валюта в Карбюраторном округе! Но Молния Маккуин решил не унывать. Он запомнил все цены на детали и поехал домой за гаечками.

Естественно, на момент прибытия домой, Молния почти все забыл. Единственное, что он помнил про каждую деталь --- диапазон цен, которому принадлежит истинная цена. Другими словами, про деталь с номером $i$ Молния знает, что ее стоимость не меньше чем $a_i$ и не больше чем $b_i$ гаечек. Гаечки в Карбюраторном округе бывают номиналом в 2ドル^k$ условные единицы, где $k \ge 0$.

Маккуину стало интересно, какое минимальное количество гаечек нужно взять, чтобы можно было расплатиться за всю покупку без сдачи при любых стоимостях из указанных диапазонов. Поскольку Молния Маккуин очень успешный гонщик, можно считать, что гаечек каждого номинала у него неограниченно много.

입력

В первой строке входных данных дано число $n$ (1ドル \le n \le 10^5$) --- количество покупок. Дальше следует $n$ строк. В $i+1$-й строке даны числа $a_i,ドル $b_i$ (1ドル \le a_i \le b_i \le 10^9$) --- диапазон стоимостей $i$-й детали.

출력

Выведите минимальное число гаечек, которое нужно взять, чтобы расплатиться за всю покупку без сдачи при любых стоимостях из указанных диапазонов.

제한

힌트