Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FIBVAL - VOI 2012 Bản vanxơ Fibonacci

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/fibval


Bản vanxơ Fibonacci là một bản nhạc mà giai điệu của nó bắt nguồn từ một trong những dãy số nổi tiếng nhất trong Lý thuyết số - dãy số Fibonacci. Hai số đầu tiên của dãy là số 1 và số 2, các số tiếp theo được xác định bằng tổng của 2 số liên tiếp ngay trước nó trong dãy.

Bản vanxơ Fibonacci thu được bằng việc chuyển dãy số Fibonacci thành dãy các nốt nhạc theo qui tắc chuyển một số nguyên dương thành nốt nhạc sau đây:

  • Số 1 tương ứng với nốt Đô (C).
  • Số 2 tương ứng với nốt Rê (D).
  • Số 3 tương ứng với nốt Mi (E).
  • Số 4 tương ứng với nốt Fa (F).
  • Số 5 tương ứng với nốt Sol (G).
  • Số 6 tương ứng với nốt La (A).
  • Số 7 tương ứng với nốt Si (B).
  • Số 8 tương ứng với nốt Đô (C).
  • Số 9 tương ứng với nốt Rê (D).


và cứ tiếp tục như vậy. Ví dụ, dãy gồm 6 số Fibonacci đầu tiên 1, 2, 3, 5, 8 và 13 tương ứng với dãy các nốt nhạc C, D, E, G, C và A.

Để xây dựng nhịp điệu vanxơ người ta đi tìm các đoạn nhạc có tính chu kỳ trong bản vanxơ Fibonacci. Đoạn nhạc được gọi là có tính chu kỳ nếu như có thể chia nó ra thành k ≥ 2 đoạn giống hệt nhau. Ví dụ, đoạn nhạc GCAGCA là đoạn có tính chu kỳ, vì nó gồm 2 đoạn giống nhau GCA.

Yêu cầu: Cho trước hai số nguyên dương u, v (u < v), hãy xác định độ dài đoạn nhạc dài nhất có tính chu kỳ của bản nhạc gồm dãy các nốt nhạc của bản vanxơ Fibonacci bắt đầu từ vị trí u kết thúc ở vị trí v.

Ràng buộc: 50% số tests ứng với 50% số điểm có ui < vi ≤ 100.

Input

  • Dòng thứ nhất chứa số nguyên dương k (k ≤ 100) là số lượng test.
  • Dòng thứ i trong số k dòng tiếp theo chứa 2 số nguyên dương ui, vi được ghi cách nhau bởi dấu cách (ui < vi ≤ 109) là vị trí bắt đầu và kết thúc của 1 bản nhạc.

Output

Ghi ra k dòng, dòng thứ i chứa 1 số nguyên là độ dài đoạn nhạc tìm được tương ứng với test thứ i. Nếu không tìm được đoạn nào có tính chu kỳ thì ghi ra số -1.

Example

Input:
2
1 3
4 10 Output: -1
2

Được gửi lên bởi:VOJ Team
Ngày:2012-01-21
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2012

hide comments
2016-11-25 14:23:38 minhsn
bài khó vãi các cậu ơi :'(
2016-04-18 17:11:44
voi mà cũng có bài nhảm thế này à @@
2016-04-12 15:28:14
Tham khảo: https://binpii.wordpress.com/2016/04/12/fibval-voi-2012-ban-vanxo-fibonacci-2/
2015-12-16 13:05:22
chu kì chỉ có 7 nốt cho những ai tưởng 13 phải ra F
2015-03-15 12:34:05 to_yeu_mao_hieu_dong
chán bài này quá, cơ bản mà code 3 lần mới ac
2015-02-17 03:00:10 Bee
bài này nằm trong cuốn BT Chuyên Tin Q1 của HSĐ / tr.25.
2014-12-18 08:35:56 *
đề cho khó hiểu vai~
2014-12-18 08:35:56 *
đề cho khó hiểu vai~
2014-07-19 15:37:43 :((
a dung mà ong lấy 13 mod 7 +1 là ra
2014-07-19 11:43:08 Chuyên Nhật CNN
tại sao 13 nó lại ra A ;-; tưởng phải ra F chứ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.